ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Tensor Methods: Numerical and Computational Aspects

Tue 16:00–16:30, Room AV 00.17
Manifold optimization for low rank matrix and tensor completion
Bart Vandereycken (University of Geneva)

The minimisation of a smooth objective function subject to (matrix) rank constraints can sometimes be very effectively solved by methods from Riemannian optimisation. This is for instance the case with the low-rank matrix/tensor completion/sensing problems. However, the standard theory of Riemannian optimisation leaves some questions unanswered regarding its theoretical and practical application. In this talk, we focus on how the (Riemannian) metric has a significant impact on the convergence of the numerical methods. In addition, we present a convergence analysis for the matrix sensing problem: given a linear sensing operator $\mathcal{A} \colon \mathbb{R}^{n \times n} \to \mathbb{R}^d$, how many observations $b = \mathcal{A}(X)$ are needed to recover the unknown rank $k$ matrix $X$? In case $\mathcal{A}$ satisfies the RIP condition, the convergence analysis can be done using standard techniques from linear algebra. This will allow us to obtain conditions on $d$ such that any sufficient-descent type Riemannian method recovers $X$. These conditions improve existing results for similar fixed rank methods for matrix sensing.