Guarantees of Riemannian Optimization for Low Rank Matrix Completion Article Swipe

MAKE IMPACT

Ke Wei , Jian‐Feng Cai , Tony F. Chan , Shingyu Leung · YOU? · · 2016 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1603.06610

We study the Riemannian optimization methods on the embedded manifold of low rank matrices for the problem of matrix completion, which is about recovering a low rank matrix from its partial entries. Assume $m$ entries of an $n\times n$ rank $r$ matrix are sampled independently and uniformly with replacement. We first prove that with high probability the Riemannian gradient descent and conjugate gradient descent algorithms initialized by one step hard thresholding are guaranteed to converge linearly to the measured matrix provided \begin{align*} m\geq C_κn^{1.5}r\log^{1.5}(n), \end{align*} where $C_κ$ is a numerical constant depending on the condition number of the underlying matrix. The sampling complexity has been further improved to \begin{align*} m\geq C_κnr^2\log^{2}(n) \end{align*} via the resampled Riemannian gradient descent initialization. The analysis of the new initialization procedure relies on an asymmetric restricted isometry property of the sampling operator and the curvature of the low rank matrix manifold. Numerical simulation shows that the algorithms are able to recover a low rank matrix from nearly the minimum number of measurements.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/1603.06610

PDF

https://arxiv.org/pdf/1603.06610

OA Status

green

Cited By

26

References

38

Related Works

10

OpenAlex ID

https://openalex.org/W2307294673

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W2307294673

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.1603.06610

Digital Object Identifier

Title

Guarantees of Riemannian Optimization for Low Rank Matrix Completion

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2016

Year of publication

Publication date

2016-03-21

Full publication date if available

Authors

Ke Wei, Jian‐Feng Cai, Tony F. Chan, Shingyu Leung

List of authors in order

Landing page

https://arxiv.org/abs/1603.06610

Publisher landing page

PDF URL

https://arxiv.org/pdf/1603.06610

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/1603.06610

Direct OA link when available

Concepts

Matrix completion, Mathematics, Combinatorics, Rank (graph theory), Matrix (chemical analysis), Low-rank approximation, Restricted isometry property, Riemannian manifold, Initialization, Gradient descent, Isometry (Riemannian geometry), Algorithm, Pure mathematics, Compressed sensing, Computer science, Gaussian, Machine learning, Materials science, Quantum mechanics, Tensor (intrinsic definition), Composite material, Programming language, Artificial neural network, Physics

Top concepts (fields/topics) attached by OpenAlex

Cited by

26

Total citation count in OpenAlex

Citations by year (recent)

2023: 2, 2022: 1, 2021: 1, 2020: 2, 2019: 5

Per-year citation counts (last 5 years)

References (count)

38

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload