Fast Low Rank column-wise Compressive Sensing

In this work, we study the following problem, that we refer to as Low Rank column-wise Compressive Sensing (LRcCS): how to recover an $n \times q$ rank-$r$ matrix, $X^* =[x^*_1 , x^*_2 ,...x^*_q]$ from $m$ independent linear projections of each of its $q$ columns, i.e., from $y_k := A_k x^*_k , k \in [q]$, when $y_k$ is an $m$-length vector. The matrices $A_k$ are known and mutually independent for different $k$. The regime of interest is low-rank, i.e., $r \ll \min(n,q)$, and undersampled measurements, i.e., $m < n$. Even though many LR recovery problems have been extensively studied in the last decade, this particular problem has received little attention so far in terms of methods with provable guarantees. We introduce a novel gradient descent (GD) based solution called altGDmin. We show that, if all entries of all $A_k$s are i.i.d. Gaussian, and if the right singular vectors of $X^*$ satisfy the incoherence assumption, then $\epsilon$-accurate recovery of $X^*$ is possible with $mq > C (n+q) r^2 \log(1/\epsilon)$ total samples and $O( mq nr \log (1/\epsilon))$ time. Compared to existing work, to our best knowledge, this is the fastest solution and, for $\epsilon < 1/\sqrt{r}$, it also has the best sample complexity. Moreover, we show that a simple extension of our approach also solves LR Phase Retrieval (LRPR), which is the magnitude-only generalization of LRcCS. It involves recovering $X^*$ from the magnitudes of entries of $y_k$. We show that altGDmin-LRPR has matching sample complexity and better time complexity when compared with the (best) existing solution for LRPR.