In prior work, it was shown that high performance matrix approximation/completion was possible when only a few fully sampled columns were available of a ground truth matrix if there was appropriate side information on the rowspace of the matrix. Several applications from quantum chemistry, magnetic resonance imaging, etc. necessitate structured (versus random) sampling, but do have other domain-specific side information that can be exploited. Herein, it is shown that further complexity reduction is possible, with limited loss in performance, if one only has access to a sketch of the rowspace information. A spectral error bound is derived, which characterizes the needed dimension of the sketched side information. This bound directly considers the accuracy of the row-space information. Numerical results validate the computational efficiency and accuracy offered by the new algorithm.

A novel matrix completion problem is considered herein: observations based on fully sampled columns and quasi-polynomial side information is exploited. The framework is motivated by quantum chemistry problems wherein full matrix computation is expensive, but partial computations only lead to column information. The proposed algorithm successfully estimates the row-space of a true matrix given a priori knowledge of the true matrix. A theoretical error bound is provided, which captures the possible inaccuracies of the side information. This work designs the first provable matrix approximation algorithm using just column samples. The proposed algorithm is validated via simulations which enable the characterization of the amount of information provided by the quasi-polynomial side information.

Robust Subspace Tracking with missing data (RST-miss) has been extensively studied in the past decade. In this work we study RST-miss to the setting where the data is federated and when the over-air data communication modality is used for information exchange between the K peer nodes and the central server. To the best of our knowledge, there is no existing work in the literature. To this end, we develop the first fast, and provable algorithm that solves RST-miss in a federated over-air setting. We corroborate our theoretical claims with extensive numerical simulations.

Active, non-parametric peak detection is considered. As a use case, active source localization is examined and an uncertainty-based sampling scheme algorithm to effectively localize the peak from a few energy measurements is designed. It is shown that under very mild conditions, the source localization error with m actively chosen energy measurements scales as O(log2m/m). Numerically, it is shown that in low-sample regimes, the proposed method enjoys superior performance on several types of data and outperforms the state-of-the-art passive source localization approaches and in the low sample regime, can outperform greedy methods as well.

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.

Robust Matrix Completion (RMC) is the problem of estimating a low-rank matrix in the presence of missing entries and element-wise (sparse) outliers. In this work, we study the RMC problem with the extra assumption that the clean data is generated from either a fixed or a slowly-changing low-dimensional subspace and introduce a provably correct online algorithm for solving it. Our problem can also be interpreted as that of Robust Subspace Tracking with missing data (RST-miss); with "robust" referring to robustness to sparse outliers. Our proposed method, called NORST-miss-robust, and its guarantee both rely on the Recursive Projected Compressive Sensing (ReProCS) framework introduced in our earlier work. We also argue that NORST-miss-robust enjoys near-optimal memory complexity, tracks subspace changes with near-optimal delay, and has time complexity that is order-wise equal to that of vanilla PCA. Detailed experimental comparisons showing the practical advantages of our method are also shown.

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.

We study the problem of subspace tracking (ST) in the presence of missing data (ST-miss). In recent work, we have studied the Robust ST (RST) problem. In this work, we show that a simple modification of our solution approach for RST also provably solves ST-miss under weaker assumptions. To our knowledge, our result is the first complete guarantee for ST-miss. This means we are able to show that, under assumptions on only the algorithm inputs (input data and/or initialization), the output subspace estimates are close to the true data subspaces at all times. Our guarantees hold under mild and easily interpretable assumptions and handle time-varying subspaces (unlike all previous work). We also show that our algorithm and its extensions are fast and have competitive experimental performance when compared with existing methods.

Dynamic robust principal component analysis (PCA) refers to the dynamic (time-varying) extension of robust PCA (RPCA). It assumes that the true (uncorrupted) data lie in a low-dimensional subspace that can change with time, albeit slowly. The goal is to track this changing subspace over time in the presence of sparse outliers. We develop and study a novel algorithm, which we call simple-ReProCS, based on the recently introduced Recursive Projected Compressive Sensing (ReProCS) framework. This paper provides the first guarantee for dynamic RPCA that holds under weakened versions of standard RPCA assumptions, slow subspace change, and a lower bound assumption on most outlier magnitudes. Our result is significant because: 1) it removes the strong assumptions needed by the two previous complete guarantees for ReProCS-based algorithms; 2) it shows that it is possible to achieve significantly improved outlier tolerance, compared with all existing RPCA or dynamic RPCA solutions by exploiting the above-mentioned two simple extra assumptions; and 3) it proves that simple-ReProCS is online (after initialization), fast, and, has near-optimal memory complexity.

Robust PCA (RPCA) is the problem of separating a given data matrix into the sum of a sparse matrix and a low-rank matrix. Static RPCA is the RPCA problem in which the subspace from which the true data is generated remains fixed over time. Dynamic RPCA instead assumes that the subspace can change with time, although usually the changes are slow. We propose a Recursive Projected Compressed Sensing based algorithm called MERoP (Memory-Efficient Robust PCA) to solve the static RPCA problem. A simple extension of MERoP has been shown in our other work to also solve the dynamic RPCA problem. To the best of our knowledge, MERoP is the first online solution for RPCA that is provably correct under mild assumptions on input data and requires no assumption on intermediate algorithm estimates. Moreover, MERoP enjoys nearly-optimal memory complexity and is almost as fast as vanilla SVD. We corroborate our theoretical claims through extensive numerical experiments on both synthetic data and real videos.

Robust subspace tracking (RST) can be simply understood as a dynamic (time-varying) extension of robust PCA. More precisely, it is the problem of tracking data lying in a fixed or slowly-changing low-dimensional subspace while being robust to sparse outliers. This work develops a recursive projected compressive sensing algorithm called “Nearly Optimal RST (NORST)”, and obtains one of the first guarantees for it. We show that NORST provably solves RST under weakened standard RPCA assumptions, slow subspace change, and a lower bound on (most) outlier magnitudes. Our guarantee shows that (i) NORST is online (after initialization) and enjoys near-optimal values of tracking delay, lower bound on required delay between subspace change times, and of memory complexity; and (ii) it has a significantly improved worst-case outlier tolerance compared with all previous robust PCA or RST methods without requiring any model on how the outlier support is generated.

Dynamic robust PCA refers to the dynamic (time-varying) extension of the robust PCA (RPCA) problem. It assumes that the true (uncorrupted) data lies in a low-dimensional subspace that can change with time, albeit slowly. The goal is to track this changing subspace over time in the presence of sparse outliers. This work provides the first guarantee for dynamic RPCA that holds under weakened standard RPCA assumptions, slow subspace change and two mild assumptions. We analyze a simple algorithm based on the Recursive Projected Compressive Sensing (ReProCS) framework. Our result is significant because (i) it removes the strong assumptions needed by the two previous complete guarantees for ReProCS-based algorithms; (ii) it shows that it is possible to achieve significantly improved outlier tolerance than all existing provable RPCA methods by exploiting slow subspace change and a lower bound on outlier magnitudes; and (iii) it proves that the proposed algorithm is online, fast, and memory-efficient.

In recent work, we obtained finite sample guarantees for the problem of Principal Component Analysis (PCA) in nonisotropic and data-dependent noise. In this work, we study an important special case of this: the problem of PCA in sparse data-dependent noise with the noise depending linearly on the signal (true data) at each time. This special case occurs in many practical applications. Two examples that we describe include (a) PCA with missing data and (b) the subspace update step of an online algorithm for dynamic robust PCA called ReProCS. The full version is [1].

Principal component analysis (PCA) is one of the most widely used dimension reduction techniques. Robust PCA (RPCA) refers to the problem of PCA when the data may be corrupted by outliers. Recent work by Cands, Wright, Li, and Ma defined RPCA as a problem of decomposing a given data matrix into the sum of a low-rank matrix (true data) and a sparse matrix (outliers). The column space of the low-rank matrix then gives the PCA solution. This simple definition has led to a large amount of interesting new work on provably correct, fast, and practical solutions to RPCA. More recently, the dynamic (time-varying) version of the RPCA problem has been studied and a series of provably correct, fast, and memory-efficient tracking solutions have been proposed. Dynamic RPCA [or robust subspace tracking RST)] is the problem of tracking data lying in a (slowly) changing subspace, while being robust to sparse outliers. This paper provides an exhaustive review of the last decade of literature on RPCA and its dynamic counterpart (RST), along with describing their theoretical guarantees, discussing the pros and cons of various approaches, and providing empirical comparisons of performance and speed. A brief overview of the newer (lowrank) matrix completion (MC) literature is also provided. This refers to the problem of completing a low-rank matrix when only a subset of its entries are observed. It can be interpreted as a simpler special case of RPCA in which the indices of the outlier corrupted entries are known.