We introduce and precisely formulate the Low Rank Columnwise matrix Sensing (LRCS) problem when some of the observed data is scrambled / permuted / shuffled / unlabeled. Shuffled LRCS is a more difficult problem than just LRCS because there are three unknown variable sets and one of them is discrete. Our proposed algorithm for solving it is the first multi-block generalization of the Alternating GD and Minimization (AltGDmin) algorithm that was introduced in recent work for fast LRCS. Since this is a new problem, no solutions exist. We also develop the AltMin solution and provide extensive numerical comparisons demonstrating that the proposed AltGDmin-based method is much faster than AltMin. As baseline, we use AltGDmin-LRCS and AltMin-LRCS for a collapsed version of this problem, which becomes an LRCS problem. Our experiments show that, when the available number of measurements is small, this fails, while our proposed method works. Finally, we bound the per-iteration time complexity of our algorithm and also provide a guarantee for its initialization step.

We introduce a real-time undersampled dynamic MRI algorithm, termed FewShot-AltGDmin-MRI, that is generalizable: works for many different applications and sampling trajectories without any application-specific parameter tuning. FS-AGM-MRI operates in real-time after processing the first short mini-batch, i.e., it can provide a reconstruction of each new image frame as soon as the MRI scan data for that frame arrives. It also provides a second set of improved quality reconstructions after a short delay. We compare our algorithm against many state of the art batch MRI algorithms, including Deep Learning (DL) based ones, on 17 different retrospectively undersampled datasets and two prospective datasets. FS-AGM-MRI is the only approach that provides accurate recovery for all datasets while also being one of the fastest.

This work has two contributions. First, we introduce a provably secure (Byzantine-resilient) sample- and communication-efficient alternating gradient descent (GD) and minimization based algorithms for solving the federated low rank matrix completion (LRMC) problem. This involves learning a low rank (LR) matrix from a small subset of its entries. Second, we extend our ideas to show how a special case of our algorithms also solves another partly-decoupled vertically federated LR matrix learning problem, that is LR column-wise sensing (LRCS), also referred to as multi-task linear representation learning in the literature. Finally, we also show how our results can be extended for the LR phase retrieval problem. In all problems, we consider column-wise or vertical federation, i.e. each node observes a small subset of entries of a disjoint column sub-matrix of the entire LR matrix. For the LRMC problem, horizontal federation is equivalent since it is symmetric across rows and columns; while for the other two it is not. In all problems, the data at different nodes is heterogeneous (not identically distributed), making it harder to obtain provable guarantees.

In this work we develop a communication-efficient Byzantine-resilient algorithm for vertically federated multi-task linear representation learning, also known as low rank column-wise compressive sensing (LRCS). Our algorithm is a geometric median based resilient modification of the alternating gradient descent (GD) and minimization (altGDmin) algorithm. In case of vertically federated LRCS, the data at the different nodes is not identically distributed (heterogeneous data setting) making it harder to solve than the horizontal case which involves homogeneous data at different nodes. Under a simple heterogeneity bound on the model parameters, and a sample complexity bound that is worse than the optimal by a factor of r (r is the rank of the unknown matrix to be recovered), we are able to show that, with high probability (w.h.p.), the subspace distance between the estimate provided by our algorithm and the span of the true unknown Low Rank (LR) matrix decays exponentially with iterations until it reaches the heterogeneity bound. To our best knowledge, our result is the first LR matrix recovery result that provides a Byzantine resilient solution in the heterogenous data setting. Ideas developed here should be extendable to other heterogenous federated LR recovery problems such as LR matrix.

In this work, we develop and analyze a novel Gradient Descent (GD) based solution, called Alternating GD and Minimization (AltGDmin), for efficiently solving the low rank matrix completion (LRMC) in a federated setting. Here “efficient” refers to communication-, computation- and sample- efficiency. LRMC involves recovering ann×qrank-rmatrixX* from a subset of its entries whenr≪ min(n, q). Our theoretical bounds on the sample complexity and iteration complexity of AltGDmin imply that it is the most communication-efficient solution while also been one of the most computation- and sample- efficient ones. We also extend our guarantee to the noisy LRMC setting. In addition, we show how our lemmas can be used to provide an improved sample complexity guarantee for the Alternating Minimization (AltMin) algorithm for LRMC. AltMin is one of the fastest centralized solutions for LRMC; with AltGDmin having comparable time cost even for the centralized setting.

This work studies our recently developed algorithm, decentralized alternating projected gradient descent algorithm (Dec-AltGDmin), for recovering a low rank (LR) matrix from independent column-wise linear projections in a decentralized setting. This means that the observed data is spread across L agents and there is no central coordinating node. Since this problem is non-convex and since it involves a subspace recovery step, most existing literature from decentralized optimization is not useful. We demonstrate using extensive numerical simulations and communication, time, and sample complexity comparisons that (i) existing decentralized gradient descent (GD) approaches fail, and (ii) other common solution approaches on LR recovery literature – projected GD, alternating GD and alternating minimization (AltMin) – either have a higher communication (and time) complexity or a higher sample complexity. Communication complexity is often the most important concern in decentralized learning.

We study how representation learning can improve the learning efficiency of contextual bandit problems. We study the setting where we play T linear contextual bandits with dimension simultaneously, and these T bandit tasks collectively share a common linear representation with a dimensionality of r ≪ d. We present a new algorithm based on alternating projected gradient descent (GD) and minimization estimator to recover a low-rank feature matrix. We obtain constructive provable guarantees for our estimator that provide a lower bound on the required sample complexity and an upper bound on the iteration complexity (total number of iterations needed to achieve a certain error level). Using the proposed estimator, we present a multi-task learning algorithm for linear contextual bandits and prove the regret bound of our algorithm. We presented experiments and compared the performance of our algorithm against benchmark algorithms.

This work introduces a Byzantine resilient solution for learning low-dimensional linear representation. Our main contribution is the development of a provably Byzantine-resilient AltGDmin algorithm for solving this problem in a federated setting. We argue that our solution is sample-efficient, fast, and communicationefficient. In solving this problem, we also introduce a novel secure solution to the federated subspace learning meta-problem that occurs in many different applications.

This work studies the problem of reliably estimating a subspace in a federated setting, when some nodes' outputs can be compromised by Byzantine attacks. Typically, the subspace of interest is the principal subspace of an unknown symmetric matrix. Each node has access to data that can be used to estimate this matrix and its principal subspace. This meta-problem occurs in various applications; two important examples are federated PCA, and the spectral initialization step of iterative solutions to various low-rank (LR) matrix recovery problems in federated settings. We introduce a novel solution framework called Subspace- Median to solve this problem in a provably Byzantine-resilient, and communication-efficient fashion.

This work considers two related learning problems in a federated attack-prone setting – federated principal components analysis (PCA) and federated low rank column-wise sensing (LRCS). The node attacks are assumed to be Byzantine which means that the attackers are omniscient and can collude. We introduce a novel provably Byzantine-resilient communication-efficient and sample-efficient algorithm, called Subspace-Median, that solves the PCA problem and is a key part of the solution for the LRCS problem. We also study the most natural Byzantine-resilient solution for federated PCA, a geometric median based modification of the federated power method, and explain why it is not useful. Our second main contribution is a complete alternating gradient descent (GD) and minimization (altGDmin) algorithm for Byzantine-resilient horizontally federated LRCS and sample and communication complexity guarantees for it. Extensive simulation experiments are used to corroborate our theoretical guarantees. The ideas that we develop for LRCS are easily extendable to other LR recovery problems as well.

This note provides a significantly simpler and shorter proof of our sample complexity guarantee for solving the low rank column-wise sensing problem using the Alternating Gradient Descent (GD) and Minimization (AltGDmin) algorithm. AltGDmin was developed and analyzed for solving this problem in our recent work. We also provide an improved guarantee.

A plethora of modern machine learning tasks require the utilization of large-scale distributed clusters as a critical component of the training pipeline. However, abnormal Byzantine behavior of the worker nodes can derail the training and compromise the quality of the inference. Such behavior can be attributed to unintentional system malfunctions or orchestrated attacks; as a result, some nodes may return arbitrary results to the parameter server (PS) that coordinates the training. Recent work considers a wide range of attack models and has explored robust aggregation and/or computational redundancy to correct the distorted gradients. In this work, we consider attack models ranging from strong ones:$q$omniscient adversaries with full knowledge of the defense protocol that can change from iteration to iteration to weak ones:$q$randomly chosen adversaries with limited collusion abilities which only change every few iterations at a time. Our algorithms rely on redundant task assignments coupled with detection of adversarial behavior. We also show the convergence of our method to the optimal point under common assumptions and settings considered in literature. For strong attacks, we demonstrate a reduction in the fraction of distorted gradients ranging from 16%–99% as compared to the prior state-of-the-art. Our top-1 classification accuracy results on the CIFAR-10 data set demonstrate 25% advantage in accuracy (averaged over strong and weak scenarios) under the most sophisticated attacks compared to state-of-the-art methods.

In recent work , we developed a fast, memory-efficient, and sample-efficient solution to the Low Rank column-wise Compressive Sensing (LRcCS) problem: recover an n × q LR matrix from m under-sampled linear projections of each of its columns. Here, undersampled means m ≪ n,q . The matrix LR model and the corresponding algorithms have two important limitations. First, for real image sequences, the required memory complexity is prohibitive. Secondly, for image or volume image sequences, it requires vectorizing the image or volume as one column of a matrix and this ignores the inherent 2D or 3D structure of the images or volumes. To address these limitations, in this work, we explore the use of a tensor LR model on the image sequence along with developing a fast and memory-efficient gradient descent (GD) based recovery algorithm and evaluating it experimentally.

This work studies our recently developed decentralized algorithm, decentralized alternating projected gradient descent algorithm, called Dec-AltProjGDmin, for solving the following low-rank (LR) matrix recovery problem: recover an LR matrix from independent column-wise linear projections (LR column-wise Compressive Sensing). In recent work, we presented constructive convergence guarantees for Dec-AltProjGDmin under simple assumptions. By "constructive", we mean that the convergence time lower bound is provided for achieving any error level ε. However, our guarantee was stated for the equal neighbor consensus algorithm (at each iteration, each node computes the average of the data of all its neighbors) while most existing results do not assume the use of a specific consensus algorithm, but instead state guarantees in terms of the weights matrix eigenvalues. In order to compare with these results, we first modify our result to be in this form. Our second and main contribution is a theoretical and experimental comparison of our new result with the best existing one from the decentralized GD literature that also provides a convergence time bound for values of ε that are large enough. The existing guarantee is for a different problem setting and holds under different assumptions than ours and hence the comparison is not very clear cut. However, we are not aware of any other provably correct algorithms for decentralized LR matrix recovery in any other settings either.

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.

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.

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 note corrects a few errors in the proof of the main result of the article “Provable Low Rank Phase Retrieval.” The result itself has no change. This article introduced an alternating minimization solution, called AltMinLowRaP, for solving the Low Rank Phase Retrieval (LRPR) problem: recover an$n \times q$matrix${{X}^{*}}$of rank$r$from${y}_{k}:= |{A}_{k}'{x}^{*}_{k}|, k=1,2, {\dots }, q$when the measurement matrices$ {A}_{k}$are mutually independent. Here$ {y}_{k}$is an$m$length vector,$ {A}_{k}$is an$n \times m$matrix, and$'$denotes transpose.

Distributed matrix computations are well-recognized to suffer from the problem of stragglers (slow or failed worker nodes). The majority of prior work in this area has presented straggler mitigation strategies that are (i) either sub-optimal in terms of their straggler resilience, or (ii) suffer from numerical problems, i.e., there is a blow-up of round-off errors in the decoded result owing to the high condition numbers of the corresponding decoding matrices. This work introduces a novel solution framework, based on embedding the computations into the structure of a convolutional code, that removes these limitations. Our approach is provably optimal in terms of its straggler resilience, and has excellent numerical robustness which can be theoretically quantified by deriving a computable upper bound on the worst case condition number over all possible decoding matrices. All above claims are backed up by extensive experiments done on the AWS cloud platform.

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.

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.

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.

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.

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 consider the problem of super-resolution for sub-diffraction imaging. We adapt conventional Fourier ptychographic approaches, for the case where the images to be acquired have an underlying structured sparsity. We propose some sub-sampling strategies which can be easily adapted to existing ptychographic setups. We then use a novel technique called CoPRAM with some modifications, to recover sparse (and block sparse) images from sub-sampled pty-chographic measurements. We demonstrate experimentally that this algorithm performs better than existing phase retrieval techniques, in terms of quality of reconstruction, using fewer number of samples.

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.

In this paper, we introduce a novel algorithmic framework for sub-diffractive super-resolution imaging of dynamic, time-varying targets. We extend recent works in low rank Fourier ptychographic imaging, to incorporate model-correction schemes, which correct for errors propagated due to inaccuracies in fitting an exact low rank model to the target video acquired. Through our algorithm, we are able to demonstrate superior reconstruction quality of video from phaseless Fourier ptychographic measurements, at low sample complexities, as compared to conventional ptychographic setups.

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].

The papers in this special issue introduce the reader to the theory, algorithms, and applications of principal component analysis (PCA) and its many extensions. The aim of PCA is to reduce the dimensionality of multivariate data while preserving as much of the relevant information as possible. It is often the first step in various types of exploratory data analysis, predictive modeling, and classification and clustering tasks, and finds applications in biomedical imaging, computer vision, process fault detection, recommendation systems’ design, and many more domains.

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.

Video denoising refers to the problem of removing “noise” from a video sequence. Here, the term “noise” is used in a broad sense to refer to any corruption or outlier or interference that is not the quantity of interest. We develop a novel solution framework, which we call layering denoising (LD), for denoising highly noisy or otherwise corrupted videos that are well modeled as the sum of a low-rank matrix plus a sparse matrix. We show that the performance of existing state-of-the-art denoisers can be significantly improved (especially in large noise settings) if the video is first decomposed into the two layers and the denoiser is applied on each layer separately. Our proposed solution uses a recursive projected compressive sensing (ReProCS) based algorithm for the layering task and video block matching and three-dimensional filtering for denoising each layer. We show the power of our proposed approach, ReProCS-LD, using exhaustive experimental comparisons.

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.

In this work we develop and study a novel online robust principal components’ analysis (RPCA) algorithm based on the recently introduced ReProCS framework. Our algorithm significantly improves upon the original ReProCS algorithm and it also returns even more accurate offline estimates. The key contribution of this work is a correctness result for this algorithm under relatively mild assumptions. By using extra (but usually valid) assumptions we are able to remove one important limitation of batch RPCA results and two important limitations of a recent result for ReProCS for online RPCA. To the best of our knowledge, this work is among the first correctness results for online RPCA.

Given a matrix of observed data, Principal Components Analysis (PCA) computes a small number of orthogonal directions that contain most of its variability. Provably accurate solutions for PCA have been in use for a long time. However, to the best of our knowledge, all existing theoretical guarantees for it assume that the data and the corrupting noise are mutually independent, or at least uncorrelated. This is valid in practice often, but not always. In this paper, we study the PCA problem in the setting where the data and noise can be correlated. Such noise is often also referred to as ``data-dependent noise". We obtain a correctness result for the standard eigenvalue decomposition (EVD) based solution to PCA under simple assumptions on the data-noise correlation. We also develop and analyze a generalization of EVD, cluster-EVD, that improves upon EVD in certain regimes.

We study the problem of sequentially recovering a sparse vector xtand a vector from a low-dimensional subspace ℓtfrom knowledge of their sum mt= xt+ ℓt. If the primary goal is to recover the low-dimensional subspace where the ℓt's lie, then the problem is one of online or recursive robust principal components analysis (PCA). To the best of our knowledge, this is the first correctness result for this problem. We prove that if a good estimate of the initial subspace is available; the ℓt's obey certain denseness and slow subspace change assumptions; and the support of xtchanges either at every frame or at least every so often, then with high probability, the support of xtwill be recovered exactly, and the error made in estimating xtand ℓtwill be small. An example where this problem occurs is in separating a sparse foreground and a slowly changing dense background from surveillance videos.

“To be considered for an 2015 IEEE Jack Keil Wolf ISIT Student Paper Award.” This work studies two interrelated problems - online robust PCA (RPCA) and online matrix completion (MC). Both problems assume that an accurate estimate of the low-dimensional subspace from which the first true data vector is generated is available. We develop a practical modification of a recently proposed algorithm to solve both problems; and we obtain correctness results for the proposed algorithms under mild assumptions.

In this paper, we obtain performance guarantees for modified-CS and for its improved version, modified-CS-Add-LS-Del, for recursive reconstruction of a time sequence of sparse signals from a reduced set of noisy measurements available at each time. Under mild assumptions, we show that the support recovery error of both algorithms is bounded by a time-invariant and small value at all times. The same is also true for the reconstruction error. Under a slow support change assumption: 1) the support recovery error bound is small compared with the support size and 2) our results hold under weaker assumptions on the number of measurements than what l1minimization for noisy data needs. We first give a general result that only assumes a bound on support size, number of support changes, and number of small magnitude nonzero entries at each time. Later, we specialize the main idea of these results for two sets of signal change assumptions that model the class of problems in which a new element that is added to the support either gets added at a large initial magnitude or its magnitude slowly increases to a large enough value within a finite delay. Simulation experiments are shown to back up our claims.

This paper designs and evaluates a practical algorithm, called Prac-ReProCS, for recovering a time sequence of sparse vectors Stand a time sequence of dense vectors Ltfrom their sum, Mt:= St+ Lt, when any subsequence of the Lt's lies in a slowly changing low-dimensional subspace. A key application where this problem occurs is in video layering where the goal is to separate a video sequence into a slowly changing background sequence and a sparse foreground sequence that consists of one or more moving regions/objects. Prac-ReProCS is the practical analog of its theoretical counterpart that was studied in our recent work.

In recent work, robust PCA has been posed as a problem of recovering a low-rank matrix L and a sparse matrix S from their sum, M := L + S and a provably exact convex optimization solution called PCP has been proposed. Suppose that we have a partial estimate of the column subspace of the low rank matrix L. Can we use this information to improve the PCP solution, i.e. allow recovery under weaker assumptions? We propose here a simple modification of the PCP idea, called modified-PCP, that allows us to use this knowledge. We derive its correctness result which shows that modified-PCP indeed requires significantly weaker incoherence assumptions than PCP, when the available subspace knowledge is accurate. Extensive simulations are also used to illustrate this. Finally, we explain how this problem naturally occurs in many applications involving time series data, e.g. in separating a video sequence into foreground and background layers, in which the subspace spanned by the background images is not fixed but changes over time and the changes are gradual. A corollary for this case is also given.

Online or recursive robust PCA can be posed as a problem of recovering a sparse vector, S t , and a dense vector, L t , which lies in a slowly changing low-dimensional subspace, from M t := S t +L t on-the-fly as new data comes in. For initialization, it is assumed that an accurate knowledge of the subspace in which L 0 lies is available. In recent works, Qiu et al proposed and analyzed a novel solution to this problem called recursive projected compressed sensing or ReProCS. In this work, we relax one limiting assumption of Qiu et al's result. Their work required that the L t 's be mutually independent over time. However this is not a practical assumption, e.g., in the video application, L t is the background image sequence and one would expect it to be correlated over time. In this work we relax this and allow the L t 's to follow an autoregressive model. We are able to show that under mild assumptions and under a denseness assumption on the unestimated part of the changed subspace, with high probability (w.h.p.), ReProCS can exactly recover the support set of S t at all times; the reconstruction errors of both S t and L t are upper bounded by a time invariant and small value; and the subspace recovery error decays to a small value within a finite delay of a subspace change time.

This paper studies the recursive robust principal components analysis problem. If the outlier is the signal-of-interest, this problem can be interpreted as one of recursively recovering a time sequence of sparse vectors, St, in the presence of large but structured noise, Lt. The structure that we assume on Lt is that Lt is dense and lies in a low-dimensional subspace that is either fixed or changes slowly enough. A key application where this problem occurs is in video surveillance where the goal is to separate a slowly changing background (Lt) from moving foreground objects (St) on-the-fly. To solve the above problem, in recent work, we introduced a novel solution called recursive projected CS (ReProCS). In this paper, we develop a simple modification of the original ReProCS idea and analyze it. This modification assumes knowledge of a subspace change model on the Lt's. Under mild assumptions and a denseness assumption on the unestimated part of the subspace of Lt at various times, we show that, with high probability, the proposed approach can exactly recover the support set of St at all times, and the reconstruction errors of both St and Lt are upper bounded by a time-invariant and small value. In simulation experiments, we observe that the last assumption holds as long as there is some support change of St every few frames.

We study the recursive robust principal components' analysis (PCA) problem. Here, “robust” refers to robustness to both independent and correlated sparse outliers. If the outlier is the signal-of-interest, this problem can be interpreted as one of recursively recovering a time sequence of sparse vectors, St, in the presence of large but structured noise, Lt: the noise needs to lie in a “slowly changing” low dimensional subspace. We study a novel solution called Recursive Projected CS (ReProCS). Under mild assumptions, we show that, with high probability (w.h.p.), at all times, ReProCS can exactly recover the support set of St; and the reconstruction errors of both Stand Ltare upper bounded by a time-invariant and small value.

In this work, we develop algorithms for tracking time sequences of sparse spatial signals with slowly changing sparsity patterns, and other unknown states, from a sequence of nonlinear observations corrupted by (possibly) non-Gaussian noise. A key example of the above problem occurs in tracking moving objects across spatially varying illumination changes, where motion is the small dimensional state while the illumination image is the sparse spatial signal satisfying the slow-sparsity-pattern-change property.

The goal of this work is to recover a sequence of sparse vectors, st; and a sequence of dense vectors, ℓt, that lie in a “slowly changing” low dimensional subspace, from time-varying undersampled linear projections of their sum. This type of problem typically occurs when the quantity being imaged can be split into a sum of two layers, one of which is sparse and the other is low-dimensional. A key application where this problem occurs is in undersampled functional magnetic resonance imaging (fMRI) to detect brain activation patterns in response to a stimulus. The brain image at time t can be modeled as being a sum of the active region image, st, (equal to the activation in the active region and zero everywhere else) and the background brain image, ℓt, which can be accurately modeled as lying in a slowly changing low dimensional subspace. We introduce a novel solution approach called matrix completion projected compressive sensing or MatComProCS. Significantly improved performance of MatComProCS over existing work is shown for the undersampled fMRI based brain active region detection problem.

We study the problem of recursively recovering a time sequence of sparse vectors, St, from measurements Mt:= St+ Ltthat are corrupted by structured noise Ltwhich is dense and can have large magnitude. The structure that we require is that Ltshould lie in a low dimensional subspace that is either fixed or changes “slowly enough” and the eigenvalues of its covariance matrix are “clustered”. We do not assume any model on the sequence of sparse vectors. Their support sets and their nonzero element values may be either independent or correlated over time (usually in many applications they are correlated). The only thing required is that there be some support change every so often. We introduce a novel solution approach called Recursive Projected Compressive Sensing with cluster-PCA (ReProCS-cPCA) that addresses some of the limitations of earlier work. Under mild assumptions, we show that, with high probability, ReProCS-cPCA can exactly recover the support set of Stat all times; and the reconstruction errors of both Stand Ltare upper bounded by a time-invariant and small value.

In this work, we obtain performance guarantees for modified-CS and for its improved version, modified-CS-Add-LS-Del, for recursive reconstruction of sparse signal sequences from noisy measurements. Under mild assumptions, and for a realistic signal change model, we show that the support recovery error of both algorithms is bounded by a time-invariant and small value at all times. The same is also true for the reconstruction error. Under a slow support change assumption, our results hold under weaker assumptions on the number of measurements than what simple compressive sensing (basis pursuit denoising) needs. Also, the result for modified-CS-add-LS-del holds under weaker assumptions on the signal magnitude increase rate than the result for modified-CS. Similar results were obtained in an earlier work, however the signal change model assumed there was very simple and not practically valid.

In this correspondence, our goal is to develop a visual tracking algorithm that is able to track moving objects in the presence of illumination variations in the scene and that is robust to occlusions. We treat the illumination and motion ( x-y translation and scale) parameters as the unknown "state" sequence. The observation is the entire image, and the observation model allows for occasional occlusions (modeled as outliers). The nonlinearity and multimodality of the observation model necessitate the use of a particle filter (PF). Due to the inclusion of illumination parameters, the state dimension increases, thus making regular PFs impractically expensive. We show that the recently proposed approach using a PF with a mode tracker can be used here since, even in most occlusion cases, the posterior of illumination conditioned on motion and the previous state is unimodal and quite narrow. The key idea is to importance sample on the motion states while approximating importance sampling by posterior mode tracking for estimating illumination. Experiments demonstrate the advantage of the proposed algorithm over existing PF-based approaches for various face and vehicle tracking. We are also able to detect illumination model changes, e.g., those due to transition from shadow to sunlight or vice versa by using the generalized expected log-likelihood statistics and successfully compensate for it without ever loosing track.

In this work, we study the application of compressive sensing (CS) based approaches for blood oxygenation level dependent (BOLD) contrast functional MR imaging (fMRI). In particular, we show, via exhaustive experiments on actual MR scanner data for brain fMRI, that our recently proposed approach for recursive reconstruction of sparse signal sequences, modified-CS-residual, outperforms other existing CS based approaches. Modified-CS-residual exploits the fact that the sparsity pattern of brain fMRI sequences and their signal values change slowly over time. It provides a fast, yet accurate, reconstruction approach that is able to accurately track the changes of the active pixels, while using only about 30% measurements per frame. Significantly improved performance over existing work is shown in terms of practically relevant metrics such as active pixel time courses, activation maps and receiver operating characteristic (ROC) curves.

This work proposes a causal and recursive algorithm for solving the “robust” principal components' analysis problem. We primarily focus on robustness to correlated outliers. In recent work, we proposed a new way to look at this problem and showed how a key part of its solution strategy involves solving a noisy compressive sensing (CS) problem. However, if the support size of the outliers becomes too large, for a given dimension of the current principal components' space, then the number of “measurements” available for CS may become too small. In this work, we show how to address this issue by utilizing the correlation of the outliers to predict their support at the current time; and using this as “partial support knowledge” for solving Modified-CS instead of CS.

In this work, we study the problem of reconstructing a sparse signal from a limited number of linear `incoherent' noisy measurements, when a part of its support is known. The known part of the support may be available from prior knowledge or from the previous time instant (in applications requiring recursive reconstruction of a time sequence of sparse signals, e.g. dynamic MRI). We study a modification of Basis Pursuit Denoising (BPDN) and bound its reconstruction error. A key feature of our work is that the bounds that we obtain are computable. Hence, we are able to use Monte Carlo to study their average behavior as the size of the unknown support increases. We also demonstrate that when the unknown support size is small, modified-BPDN bounds are much tighter than those for BPDN, and hold under much weaker sufficient conditions (require fewer measurements).

Our goal is to develop statistical models for the shape change of a configuration of "landmark" points (key points of interest) over time and to use these models for filtering and tracking to automatically extract landmarks, synthesis, and change detection. The term "shape activity" was introduced in recent work to denote a particular stochastic model for the dynamics of landmark shapes (dynamics after global translation, scale, and rotation effects are normalized for). In that work, only models for stationary shape sequences were proposed. But most "activities" of a set of landmarks, e.g., running, jumping, or crawling, have large shape changes with respect to initial shape and hence are nonstationary. The key contribution of this work is a novel approach to define a generative model for both 2D and 3D nonstationary landmark shape sequences. Greatly improved performance using the proposed models is demonstrated for sequentially filtering noise-corrupted landmark configurations to compute Minimum Mean Procrustes Square Error (MMPSE) estimates of the true shape and for tracking human activity videos, i.e., for using the filtering to predict the locations of the landmarks (body parts) and using this prediction for faster and more accurate landmarks extraction from the current image.

We propose algorithms for tracking the boundary contour of a deforming object from an image sequence, when the nonaffine (local) deformation over consecutive frames is large and there is overlapping clutter, occlusions, low contrast, or outlier imagery. When the object is arbitrarily deforming, each, or at least most, contour points can move independently. Contour deformation then forms an infinite (in practice, very large), dimensional space. Direct application of particle filters (PF) for large dimensional problems is impractically expensive. However, in most real problems, at any given time, most of the contour deformation occurs in a small number of dimensions ("effective basis space") while the residual deformation in the rest of the state space ("residual space") is small. This property enables us to apply the particle filtering with mode tracking (PF-MT) idea that was proposed for such large dimensional problems in recent work. Since most contour deformation is low spatial frequency, we propose to use the space of deformation at a subsampled set of locations as the effective basis space. The resulting algorithm is called deform PF-MT. It requires significant modifications compared to the original PF-MT because the space of contours is a non-Euclidean infinite dimensional space.

In recent work, Kalman Filtered Compressed Sensing (KF-CS) was proposed to causally reconstruct time sequences of sparse signals, from a limited number of ldquoincoherentrdquo measurements. In this work, we develop the KF-CS idea for causal reconstruction of medical image sequences from MR data. This is the first real application of KF-CS and is considerably more difficult than simulation data for a number of reasons, for example, the measurement matrix for MR is not as ldquoincoherentrdquo and the images are only compressible (not sparse). Greatly improved reconstruction results (as compared to CS and its recent modifications) on reconstructing cardiac and brain image sequences from dynamic MR data are shown.

In recent work, we studied the problem of causally reconstructing time sequences of spatially sparse signals, with unknown and slow time-varying sparsity patterns, from a limited number of linear ldquoincoherentrdquo measurements. We proposed a solution called Kalman filtered compressed sensing (KF-CS). The key idea is to run a reduced order KF only for the current signal's estimated nonzero coefficients' set, while performing CS on the Kalman filtering error to estimate new additions, if any, to the set. KF may be replaced by least squares (LS) estimation and we call the resulting algorithm LS-CS. In this work, (a) we bound the error in performing CS on the LS error and (b) we obtain the conditions under which the KF-CS (or LS-CS) estimate converges to that of a genie-aided KF (or LS), i.e. the KF (or LS) which knows the true nonzero sets.

In this work, we propose algorithms to recursively and causally reconstruct a sequence of natural images from a reduced number of linear projection measurements taken in a domain that is ¿incoherent¿ with respect to the image's sparsity basis (typically wavelet) and demonstrate their application in real-time MR image reconstruction. For a static version of the above problem, Compressed Sensing (CS) provides a provably exact and computationally efficient solution. But most existing solutions for the actual problem are either offline and non-causal or cannot compute an exact reconstruction (for truly sparse signal sequences), except using as many measurements as those needed for CS. The key idea of our proposed solution (modified-CS) is to design a modification of CS when a part of the support set is known (available from reconstructing the previous image). We demonstrate the exact reconstruction property of modified-CS on full-size image sequences using much fewer measurements than those required for CS. Greatly improved performance over existing work is demonstrated for approximately sparse signals or noisy measurements.

We study the problem of reconstructing a sparse signal from a limited number of its linear projections when a part of its support is known. This may be available from prior knowledge. Alternatively, in a problem of recursively reconstructing time sequences of sparse spatial signals, one may use the support estimate from the previous time instant as the ldquoknownrdquo part of the support. The idea of our solution (modified-CS) is to solve a convex relaxation of the following problem: find the signal that satisfies the data constraint and whose support contains the smallest number of new additions to the known support. We obtain sufficient conditions for exact reconstruction using modified-CS. These turn out to be much weaker than those needed for CS, particularly when the known part of the support is large compared to the unknown part.

We have proposed a novel model-based compression technique for nonstationary landmark shape data extracted from video sequences. The main goal is to develop a technique for the compact storage of landmark shape data. We use nonstationary shape activity (NSSA) to model the shape sequences. The shape data is encoded by applying differential pulse code modulation (DPCM) on the shape velocity coefficients under the NSSA model. We have studied the system performance in terms of compressibility-distortion trade off. NSSA based compression technique has been compared with two other methods based on existing shape modeling techniques namely, stationary shape activity (SSA) and active shape model (ASM). We tested our system with landmark shape data extracted from multiple video sequences of the CMU mocap database. It was found that NSSA outperforms both SSA and ASM in terms of compressibility for a given distortion tolerance. Thus NSSA based compression technique could be very useful in the applications like storage of large volumes of biomedical landmarks' data.

In previous work, we developed the Illum-PF-MT, which is the PF-MT idea applied to the problem of tracking temporally and spatially varying illumination change. In many practical problems, the rate at which illumination changes varies over time. For e.g. when a car transitions from shadow to sunlight or vice-versa the rate of illumination change is much higher than when it is in shadow or in sunlight. One way to model illumination change in such problems is using a Gaussian random walk model with two values of the change covariance - a large covariance when a "transition" is detected and a much smaller one when "no transition" is detected. But to use such a model, one needs to first detect the transition. The transition is a natural one and so it happens gradually (unlike a sudden manual dimming of the light in the room) and thus existing change detection statistics which are designed only for sudden changes are unable to detect the transition. In this paper, we propose to use the recently proposed generalized ELL (gELL) idea which uses the tracked part of the change to detect it and hence detects such partially trackable changes very quickly. Since gELL detects much before loss of track occurs, one is able to transition to the "transition" model and back without ever losing track. Also, for the first time, we demonstrate the use of gELL in combination with the PF-MT algorithm which is more stable to model change than the original PF.

We consider the problem of reconstructing time sequences of spatially sparse signals (with unknown and time-varying sparsity patterns) from a limited number of linear "incoherent" measurements, in real-time. The signals are sparse in some transform domain referred to as the sparsity basis. For a single spatial signal, the solution is provided by Compressed Sensing (CS). The question that we address is, for a sequence of sparse signals, can we do better than CS, if (a) the sparsity pattern of the signal's transform coefficients' vector changes slowly over time, and (b) a simple prior model on the temporal dynamics of its current non-zero elements is available. The overall idea of our solution is to use CS to estimate the support set of the initial signal's transform vector. At future times, run a reduced order Kalman filter with the currently estimated support and estimate new additions to the support set by applying CS to the Kalman innovations or filtering error (whenever it is "large").

We present a novel framework for tracking of a long sequence of human activities, including the time instances of change from one activity to the next, using a closed-loop, non-linear dynamical feedback system. A composite feature vector describing the shape, color and motion of the objects, and a non-linear, piecewise stationary, stochastic dynamical model describing its spatio-temporal evolution, are used for tracking. The tracking error or expected log likelihood, which serves as a feedback signal, is used to automatically detect changes and switch between activities happening one after another in a long video sequence. Whenever a change is detected, the tracker is re initialized automatically by comparing the input image with learned models of the activities. Unlike some other approaches that can track a sequence of activities, we do not need to know the transition probabilities between the activities, which can be difficult to estimate in many application scenarios. We demonstrate the effectiveness of the method on multiple indoor and outdoor real-life videos and analyze its performance.

In recent work, the authors introduced a multiplicative, low dimensional model of illumination that is computed as a linear combination of a set of simple-to-compute Legendre basis functions. The basis coefficients describing illumination change, are can be combined with the "shape" vector to define a joint "shape"-illumination space for tracking. The increased dimensionality of the state vector necessitates an increase in the number of particles required to maintain tracking accuracy. In this paper, we utilize the recently proposed PF-MT algorithm to estimate the illumination vector. This is motivated by the fact that, except in case of occlusions, multimodality of the state posterior is usually due to multimodality in the "shape" vector (e.g. there may be multiple objects in the scene that roughly match the template). In other words, given the "shape" vector at time t, the posterior of the illumination (probability distribution of illumination conditioned on the "shape" and illumination at previous time) is unimodal. In addition, it is also true that this posterior is usually quite narrow since illumination changes over time are slow. The choice of the illumination model permits the illumination coefficients to be solved in closed form as a solution of a regularized least squares problem. We demonstrate the use of our method for the problem of face tracking under variable lighting conditions existing in the scene.

Consider tracking a state space model with multimodal observation likelihoods using a particle filter (PF). Under certain assumptions that imply narrowness of the state transition prior, many efficient importance sampling techniques have been proposed in literature. For large dimensional state spaces (LDSS), these assumptions may not always hold. But, it is usually true that at a given time, state change in all except a few dimensions is small. We use this fact to design a simple modification (PF-EIS) of an existing importance sampling technique. Also, importance sampling on an LDSS is expensive (requires large number of particles, N) even with the best technique. But if the "residual space" variance is small enough, we can replace importance sampling in residual space by mode tracking (PF-MT). This drastically reduces the importance sampling dimension for LDSS, hence greatly reducing the required N.

Tracking deforming objects involves estimating the global motion of the object and its local deformations as a function of time. Tracking algorithms using Kalman filters or particle filters have been proposed for finite dimensional representations of shape, but these are dependent on the chosen parametrization and cannot handle changes in curve topology. Geometric active contours provide a framework which is parametrization independent and allow for changes in topology. In the present work, we formulate a particle filtering algorithm in the geometric active contour framework that can be used for tracking moving and deforming objects. To the best of our knowledge, this is the first attempt to implement an approximate particle filtering algorithm for tracking on a (theoretically) infinite dimensional state space.

Tracking deforming objects involves estimating the global motion of the object and its local deformations as functions of time. Tracking algorithms using Kalman filters or particle filters (PFs) have been proposed for tracking such objects, but these have limitations due to the lack of dynamic shape information. In this paper, we propose a novel method based on employing a locally linear embedding in order to incorporate dynamic shape information into the particle filtering framework for tracking highly deformable objects in the presence of noise and clutter. The PF also models image statistics such as mean and variance of the given data which can be useful in obtaining proper separation of object and background.

We study particle filtering algorithms for tracking on infinite (in practice, large) dimensional state spaces. Particle filtering (Monte Carlo sampling) from a large dimensional system noise distribution is computationally expensive. But, in most large dim tracking applications, it is fair to assume that "most of the state change" occurs in a small dimensional basis and the basis itself may be slowly time varying (approximated as piecewise constant). We have proposed a PF algorithm with basis change detection and re-estimation steps that uses this idea. The implicit assumptions in defining this algorithm are very strong. We study here the implications of weaker assumptions and how to handle them. We propose to use a simple modification of the asymptotically stable adaptive particle filter to handle errors in estimating the basis dimension

We propose particle filtering algorithms for tracking on infinite (or large) dimensional state spaces. We consider the general case where state space may not be a vector space, we assume it to be a separable metric space (Polish space). In implementation, any such space is approximated by a finite but large dimensional vector, whose dimension may vary at every time. Monte Carlo sampling from a large dimensional system noise distribution is computationally expensive. Also, the number of particles required for accurate particle filtering increases with the number of independent dimensions of the system noise, making particle filtering even more expensive. But as long as the number of independent system noise dimensions is small, even if the total state space dimension is very large, a particle filtering algorithm can be implemented. In most large dim applications, it is fair to assume that "most of the state change" occurs in a small dimensional basis, which may be fixed or slowly time varying (approximated as piecewise constant). We use this assumption to propose efficient PF algorithms. These are analyzed and extended in N. Vaswani, (2006)

In order to summarize a video consisting of a sequence of different activities, there are three fundamental problems: tracking the objects of interest, detecting the activity change times and recognizing the new activity. This paper presents an algorithm for achieving all these three tasks simultaneously and presents results on how it can used for indexing and summarizing a real-life video sequence. Human activities are represented by a model for the dynamics of the shape of the human body contour. Measures are designed for detecting both gradual transitions and sudden changes between activity models.

We present a new classification algorithm, principal component null space analysis (PCNSA), which is designed for classification problems like object recognition where different classes have unequal and nonwhite noise covariance matrices. PCNSA first obtains a principal components subspace (PCA space) for the entire data. In this PCA space, it finds for each class "i," an Mi-dimensional subspace along which the class' intraclass variance is the smallest. We call this subspace an approximate null space (ANS) since the lowest variance is usually "much smaller" than the highest. A query is classified into class "i" if its distance from the class' mean in the class' ANS is a minimum. We derive upper bounds on classification error probability of PCNSA and use these expressions to compare classification performance of PCNSA with that of subspace linear discriminant analysis (SLDA). We propose a practical modification of PCNSA called progressive-PCNSA that also detects "new" (untrained classes). Finally, we provide an experimental comparison of PCNSA and progressive PCNSA with SLDA and PCA and also with other classification algorithms-linear SVMs, kernel PCA, kernel discriminant analysis, and kernel SLDA, for object recognition and face recognition under large pose/expression variation. We also show applications of PCNSA to two classification problems in video--an action retrieval problem and abnormal activity detection.

Geometric active contours are formulated in a manner which is parametrization independent. As such, they are amenable to representation as the zero level set of the graph of a higher dimensional function. This representation is able to deal with singularities and changes in topology of the contour. It has been used very successfully in static images for segmentation and registration problems where the contour (represented as an implicit curve) is evolved until it minimizes an image based energy functional. But tracking involves estimating the global motion of the object and its local deformations as a function of time. Some attempts have been made to use geometric active contours for tracking, but most of these minimize the energy at each frame and do not utilize the temporal coherency of the motion or the deformation. On the other hand, tracking algorithms using Kalman filters or particle filters have been proposed for finite dimensional representations of shape. But these are dependent on the chosen parametrization and cannot handle changes in curve topology. In the present work, we formulate a particle filtering algorithm in the geometric active contour framework that can be used for tracking moving and deforming objects.

We study the change detection problem in a general HMM when the change parameters are unknown and the change can be slow or drastic. Drastic changes can be detected easily using the increase in tracking error or the negative log of observation likelihood (OL). But slow changes usually get missed. We have proposed in past work a statistic called ELL which works for slow change detection. Now single time estimates of any statistic can be noisy. Hence we propose a modification of the cumulative sum (CUSUM) algorithm which can be applied to ELL and OL and thus improves both slow and drastic change detection performance.

The aim is to model "activity" performed by a group of moving and interacting objects (which can be people, cars, or different rigid components of the human body) and use the models for abnormal activity detection. Previous approaches to modeling group activity include co-occurrence statistics (individual and joint histograms) and dynamic Bayesian networks, neither of which is applicable when the number of interacting objects is large. We treat the objects as point objects (referred to as "landmarks") and propose to model their changing configuration as a moving and deforming "shape" (using Kendall's shape theory for discrete landmarks). A continuous-state hidden Markov model is defined for landmark shape dynamics in an activity. The configuration of landmarks at a given time forms the observation vector, and the corresponding shape and the scaled Euclidean motion parameters form the hidden-state vector. An abnormal activity is then defined as a change in the shape activity model, which could be slow or drastic and whose parameters are unknown. Results are shown on a real abnormal activity-detection problem involving multiple moving objects.

We study the errors in particle filtering with incorrect system model parameters. The total error in approximating the posterior distribution of the actual process (state), given noisy observations, can be split into modeling error and particle filtering error in tracking with the incorrect model. We show that the bound on both errors is a monotonically increasing function of the error in the system model per time step. The bound on the particle filtering error blows up very quickly since it has increasing derivatives of all orders. We apply this result to bounding the errors in approximating our statistic for slow change detection in nonlinear systems.

Monitoring activities using video data is an important surveillance problem. A special scenario is to learn the pattern of normal activities and detect abnormal events from a very low resolution video where the moving objects are small enough to be modeled as point objects in a 2D plane. Instead of tracking each point separately, we propose to model an activity by the polygonal 'shape' of the configuration of these point masses at any time t, and its deformation over time. We learn the mean shape and the dynamics of the shape change using hand-picked location data (no observation noise) and define an abnormality detection statistic for the simple case of a test sequence with negligible observation noise. For the more practical case where observation (point locations) noise is large and cannot be ignored, we use a particle filter to estimate the probability distribution of the shape given the noisy observations up to the current time. Abnormality detection in this case is formulated as a change detection problem. We propose a detection strategy that can detect both 'drastic' and 'slow' abnormalities. Our framework can be directly applied for object location data obtained using any type of sensors - visible, radar, infrared or acoustic.

Monitoring activities in a certain region from video data is an important surveillance problem. The goal is to learn the pattern of normal activities and detect unusual ones by identifying activities that deviate appreciably from the typical ones. We propose an approach using statistical shape theory based on the shape model of D.G. Kendall et al. (see "Shape and Shape Theory", John Wiley and Sons, 1999). In a low resolution video, each moving object is best represented as a moving point mass or particle. In this case, an activity can be defined by the interactions of all or some of these moving particles over time. We model this configuration of the particles by a polygonal shape formed from the locations of the points in a frame and the activity by the deformation of the polygons in time. These parameters are learned for each typical activity. Given a test video sequence, an activity is classified as abnormal if the probability for the sequence (represented by the mean shape and the dynamics of the deviations), given the model, is below a certain threshold The approach gives very encouraging results in surveillance applications using a single camera and is able to identify various kinds of abnormal behavior.

Monitoring activities in a certain region from video data is an important surveillance problem today. The goal is to learn the pattern of normal activities and detect unusual ones by identifying activities that deviate appreciably from the typical ones. In this paper we propose an approach using statistical shape theory (based on Kendall's shape model) [D.G. Kendall et al., 1999]. In a low resolution video each moving object is best represented as a moving point mass or particle. In this case, an activity can be defined by the interactions of all or some of these moving particles over time. We model this configuration of the particles by a polygonal shape formed from the locations of the points in a frame and the activity by the deformation of the polygons in time. These parameters are learnt for each typical activity. Given a test video sequence, an activity is classified as abnormal if the probability for the sequence (represented by the mean shape and the dynamics of the deviations), given the model is below a certain threshold. The approach gives very encouraging results in surveillance applications using a single camera and is able to identify various kinds of abnormal behaviors.

Remote surveillance of battlefields is an important component of future combat systems (FCS). Typically, multiple infra-red (IR) sensors are placed in the field for image acquisition from different orientations. A system for selecting a single best view image chip from an IR video sequence and compression of the chip for transmission is presented. Moving object detection was done using the algorithm described in Shekarforoush et al., (2000). Eigenspace classification has been implemented for best view selection. Fast algorithms for image chip compression have been developed in the wavelet domain by combining a non-iterative zerotree coding method with 2D-DPCM for both low and high frequency subbands and compared against existing schemes.