We study the following lesser-known low rank (LR) recovery problem: recover an$n \times q$rank-$r$matrix,${ \boldsymbol {X}}^{\ast}=[\boldsymbol {x}^{\ast}_{1}, \boldsymbol {x}^{\ast}_{2}, \ldots, \boldsymbol {x}^{\ast}_{q}]$, with$r \ll \min (n,q)$, from$m$independent linear projections of each of its$q$columns, i.e., from$\boldsymbol {y}_{k}:= \boldsymbol {A}_{k} \boldsymbol {x}^{\ast}_{k}, k \in [q]$, when$\boldsymbol {y}_{k}$is an$m$-length vector with$m < n$. The matrices$\boldsymbol {A}_{k}$are known and mutually independent for different$k$. We introduce a novel gradient descent (GD) based solution called AltGD-Min. We show that, if the$\boldsymbol {A}_{k}\text{s}$are i.i.d. with i.i.d. Gaussian entries, and if the right singular vectors of${ \boldsymbol {X}}^{\ast}$satisfy the incoherence assumption, then$\epsilon $-accurate recovery of${ \boldsymbol {X}}^{\ast}$is possible with order$(n+q) r^{2} \log (1/\epsilon)$total samples and order$mq nr \log (1/\epsilon)$time. Compared with existing work, this is the fastest solution. For$\epsilon < r^{1/4}$, it also has the best sample complexity. A simple extension of AltGD-Min also provably solves LR Phase Retrieval, which is a magnitude-only generalization of the above problem. AltGD-Min factorizes the unknown${ \boldsymbol {X}}$as${ \boldsymbol {X}}= { \boldsymbol {U}} \boldsymbol {B} $where${ \boldsymbol {U}}$and$\boldsymbol {B}$are matrices with$r$columns and rows respectively. It alternates between a (projected) GD step for updating${ \boldsymbol {U}}$, and a minimization step for updating$\boldsymbol {B}$. Its each iteration is as fast as that of regular projected GD because the minimization over$\boldsymbol {B}$decouples column-wise. At the same time, we can prove exponential error decay for it, which we are unable to for projected GD. Finally, it can also be efficiently federated with a communication cost of only$nr$per node, instead of$nq$for projected GD.

In recent work we developed a fast and sample-efficient gradient descent (GD) solution to the following "Low Rank column-wise Compressive Sensing (LRcCS)": recover an n × q, rank-r matrix X*from measurements ${{\mathbf{y}}_k} = {{\mathbf{A}}_k}{\mathbf{x}}_k^{\ast}$, $k = 1,2, \ldots ,q$ when each ykis an m-length vector with m < n, and the rank r ≪ min(n,q). Accelerated dynamic MRI is a key application where this problem occurs. In this work, we show the power of our approach (and of its modification for the MRI setting) for four very different highly undersampled dynamic MRI applications. Without any application-specific parameter tuning, in most settings, our approach outperforms the state-of-the-art MRI methods, while also being significantly faster in all settings.

In recent work, we studied the phaseless PCA (low rank phase retrieval) problem and developed a provably correct and fast alternating minimization (AltMin) solution for it called AltMinLowRaP. In this work, we develop a modification of AltMinLowRaP, called AltMinLowRaP-Ptych, that is designed for reducing the sample complexity (number of measurements required for accurate recovery) for dynamic Fourier ptychographic imaging. Fourier ptychography is a computational imaging technique that enables high-resolution microscopy using multiple low-resolution cameras. Via exhaustive experiments on real image sequences with simulated ptychographic measurements, we show the power of our algorithm for reducing the number of samples required for accurate recovery.

We study the “Low Rank column-wise Compressive Sensing (LRcCS)” problem: recover an n × q rank-r matrix, ${X^ * } = \left[ {x_1^ *,x_2^ *, \ldots x_q^ * } \right]$, with r ≪ min(n,q), from ${y_k}: = {A_k}x_k^ *,k \in [q]$, when ykis an m-length vector with mkare known and mutually independent for different k. Even though many other LR recovery problems have been extensively studied, this problem has received little attention. We introduce a novel gradient descent (GD) based solution called altGDmin, and show that, if all entries of all Aks are i.i.d. Gaussian, and if the right singular vectors of X∗satisfy the incoherence assumption, then ϵaccurate recovery of X∗is possible with mq > C(n+q)r2log(1/ϵ) total scalar samples and O(mqnrlog(1/ϵ)) time. Compared to existing work, to our best knowledge, this is the fastest solution and, for $\in < 1/\sqrt r$, it also has the best sample complexity.

This work solves the Low Rank Phase Retrieval (LRPR) problem: recover an$n\times q$rank-$r$matrix$X^{\ast}$from$y_{k}:=\vert A_{k}^{\top}x_{k}^{\ast}\vert, \ k=1,2, \ldots, q$. The different matrices$A_{k}$are i.i.d. and each contains i.i.d. standard Gaussian entries. We obtain a new guarantee for solving LRPR using the AltMin algorithm, AltMinLowRaP, that was developed and studied in our earlier work. Our result proves the following: if the right singular vectors of$X^{\ast}$satisfy the incoherence assumption, and if the total number of measurements$mq\gtrsim nr^{2}(r+\log(1/\epsilon))$, the AltMinLowRaP estimate converges geometrically to$X^{\ast}$. In addition, we also need$m\gtrsim max(r,\log q,\log n)$because of the specific asymmetric nature of our problem. Based on comparison with related well-studied problems (low-rank matrix completion and sparse PR), we argue why the above sample complexity cannot be improved any further for any non-convex (iterative) solution to LRPR.

We study the Low Rank Phase Retrieval (LRPR) problem defined as follows: recover an n X × q matrix X* of rank r from a different and independent set of m phaseless (magnitude-only) linear projections of each of its columns. To be precise, we need to recover X* from yk:= |Ak'x*k|, k = 1, 2, . . . , q when the measurement matrices Ak are mutually independent. Here ykis an m length vector, Akis an n × m matrix, and denotes matrix transpose. The question is when can we solve LRPR with m4log(1/∈), the matrices Ak contain i.i.d. standard Gaussian entries, and the right singular vectors of X* satisfy the incoherence assumption from matrix completion literature. Here C is a numerical constant that only depends on the condition number of X* and on its incoherence parameter. Its time complexity is only Cmqnr log2(1/∈). Since even the linear (with phase) version of the above problem is not fully solved, the above result is also the first complete solution and guarantee for the linear case. Finally, we also develop a simple extension of our results for the dynamic LRPR setting.

Phaseless subspace tracking is the problem of recovering a time sequence of discrete signals from magnitude-only measurements of their linear projections, when the true signal lies in a low-dimensional subspace that can change with time. A typical assumption used in a lot of work is that the subspace changes gradually over time. We define this as (i) the maximum principal angle between the old and new subspaces is not too large (less than 90 degrees) or the number directions that changes is few or both; and (ii) the delay between subspace change times is large enough. This paper presents a novel algorithm, that we call PhaST, for model-free, mini- batch and fast Phaseless Subspace Tracking. We show via experiments that PhaST is significantly faster, and significantly more memory-efficient, than an existing algorithm for low- rank phase retrieval (which can be interpreted as a batch version of phaseless subspace tracking that does not assume anything about subspace changes). When fewer measurements are available, it also has significantly better recovery performance than both LRPR and single signal phase retrieval methods when its structural assumptions are valid.

This work proposes the first set of simple, practically useful, and provable algorithms for two inter-related problems. (i) The first is low-rank matrix recovery from magnitude-only (phaseless) linear projections of each of its columns. This finds important applications in phaseless dynamic imaging, e.g., Fourier Ptychographic imaging of live biological specimens. Our guarantee shows that, in the regime of small ranks, the sample complexity required is only a little larger than the order-optimal one, and much smaller than what standard (unstructured) phase retrieval methods need. %Moreover our algorithm is fast and memory-efficient if only the minimum required number of measurements is used (ii) The second problem we study is a dynamic extension of the above: it allows the low-dimensional subspace from which each image/signal (each column of the low-rank matrix) is generated to change with time. We introduce a simple algorithm that is provably correct as long as the subspace changes are piecewise constant.

In this paper, we introduce a principled algorithmic approach for Fourier ptychographic imaging of dynamic, time-varying targets. To the best of our knowledge, this setting has not been explicitly addressed in the ptychography literature. We argue that such a setting is very natural, and that our methods provide an important first step towards helping reduce the sample complexity (and hence acquisition time) of imaging dynamic scenes to managaeble levels. With significantly reduced acquisition times per image, it is conceivable that dynamic ptychographic imaging of fast changing scenes indeeed becomes practical in the near future.

We study the problem of recovering a low-rank matrix, X, from phaseless measurements of random linear projections of its columns. We develop a novel solution approach, called AltMinTrunc, that consists of a two-step truncated spectral initialization step, followed by a three-step alternating minimization algorithm. We obtain sample complexity bounds for the AltMinTrunc initialization to provide a good approximation of the true X. When the rank of X is low enough, these are significantly smaller than what existing single vector phase retrieval algorithms need. Via extensive experiments, we demonstrate the same for the entire algorithm.