an overview of low-rank matrix recovery from incomplete observations

We are going to recover a low-rank matrix $X_0 in R^{M times N}$ from incomplete linear measurements $y in R^{L}$. The model can be expressed as follows:
$$
min rank(X) ~~ s.t. ~~y=mathcal{A}(X),
$$
where $mathcal{A} : R^{Mtimes N} to R^{L}$ is a linear measurements.

After convex relaxation, the problem becomes
$$
min ||X||_{*} ~~ s.t. ~~y=mathcal{A}(X),
$$

For Gaussian $mathcal{A}$ , the analysis is elegent and clean. There are mainly two kind of approaches solving the problem.

Based on the matrix_RIP assumption, this technique combines $epsilon$-net argument and union bound, and finally gives a bound for successful recovery. In this technique, the optimum is not fixed, that is, the result holds for all original $X_0in R^{M times N}$.

This approach gives a tighted bound by using convex geometry and Gaussian widths. However, It shoud be mentioned that the optimum $X_0$ is fixed, because the tangent cone is determined by $X_0$.

Matrix completion is a problem of recovering a low-rank matrix from a few number of its entries. This problem can be expressed as the above low-rank recovery problem. But the operater is bounded orthogonal rather than Gaussian.

The popular method to solve matrix completion is dual certificate.

In this paper, lifting is a way to recast a system of quadratic equations/Phas Retrieval/Blind Deconvolution to a system of low-rank recovery.

For this problem, we only know some magnitudes of linear measurements $y_l = |leftlangle {v_0, a_l} rightrangle | ,l=1,ldots,L$. After squaring the observations, we get
$$
y_l^2 = |leftlangle {v_0, a_l} rightrangle |^2=leftlangle {v_0 v_0^T,a_l a_l^T} rightrangle=leftlangle {X_0,A_l} rightrangle,
$$

where $X_0=v_0 v_0^T$ and $A_l=a_l a_l^T$ are rank one matrices. So this problem can be solved as
$$
min ||X||_{*} ~~ s.t. ~~ leftlangle{X,A_l}rightrangle = y_l^2, l=1,ldots,L.
$$

The obeservation model is $y=h*s$. By Fourior transform, this problem can also be recasted to low-rank recovery.