Source-linked AI summary

Recursive Robust PCA or Recursive Sparse Recovery in Large but Structured Noise

Chenlu Qiu, Namrata Vaswani, Brian Lois, Leslie Hogben

arXiv:1211.3754v10cs.ITmath.IT

TL;DR

The paper studies recursive recovery of sparse vectors amid dense, low-dimensional noise whose subspace may change, a setting motivated by separating moving foreground from video background. It analyzes ReProCS, an online method that assumes knowledge of the subspace-change model. Under its assumptions, ReProCS exactly recovers sparse-vector supports with high probability and bounds reconstruction errors by a time-invariant small value.

  • Problem

    The problem is to recover sparse vectors S_t in the presence of dense, low-dimensional L_t, with an initially estimated subspace and possible subspace changes over time.

    Source: §I · p. 1, A. Problem Definition · p. 5
  • Method

    ReProCS analyzes recursive projected compressed sensing, using projection PCA to update estimates of the low-dimensional subspace and assuming knowledge of the subspace-change model.

    Source: C. Recursive Projected CS (ReProCS) · p. 9, §X · p. 25
  • Results

    With high probability, ReProCS exactly recovers the support of S_t at all times, keeps reconstruction errors for S_t and L_t bounded by a time-invariant small value, and recovers changed subspaces within finite delay.

    Source: §X · p. 25
  • Takeaways & Limitations

    The analyzed approach targets online recovery of sparse outliers even when the dense, low-dimensional component's subspace changes over time.

    Source: §I · p. 1, §X · p. 25

    The results require assumptions on algorithm estimates and knowledge of model parameters, including subspace-change times, so neither is a correctness result.

    Source: E. Discussion · p. 19

Abstract

from arXiv · show

This work studies 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 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, we introduce a novel solution called Recursive Projected CS (ReProCS). Under mild assumptions, we show that, with high probability (w.h.p.), ReProCS 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 at all times.

I. INTRODUCTION

The paper frames recursive robust PCA as recovering sparse signals from measurements contaminated by dense, low-dimensional noise that changes slowly, a setting motivated by applications such as video surveillance. It introduces and analyzes ReProCS, with guarantees under stated subspace and denseness assumptions.

I. INTRODUCTION

  • Robust PCA addresses outliers that may be large sparse corruptions; in video, it models moving foreground as sparse outliers and a slowly changing background as dense, low-dimensional data.The paper also identifies fMRI activation, anomalous network behavior, and abnormal sensor-network events as applications where an online solution is desirable.Source: §I · p. 1

A. Related Work

  • Earlier outlier-detection and correction approaches can fail when sparse signal entries are small relative to Lt, while PCP separates low-rank and sparse components under stated assumptions.The paper presents ReProCS as an online alternative; prior experiments reported it faster than PCP and better when support changes were correlated or the background subspace dimension was large for a given support size.Source: A. Related Work · pp. 1–2

B. Our Contributions

  • Under its assumptions, ReProCS exactly recovers the support of St at all times, bounds reconstruction errors for St and Lt by a small time-invariant value, and achieves small subspace error after finite delay.The guarantees require an initial subspace estimate, a known subspace-change model, and denseness of the currently unestimated changed subspace; the latter depends on algorithm estimates.Source: B. Our Contributions · p. 2
  • ReProCS-cPCA handles a more general subspace-change model with an extra clustering assumption, without bounding the number of changes if change-point separation grows logarithmically with their count.Equivalently, it does not require a bound on the rank of Lt.Source: B. Our Contributions · p. 2
  • The paper describes ReProCS as the first analyzed recursive robust-PCA and sparse-plus-low-rank recovery algorithm, and notes that its results apply to recursive matrix completion.In matrix completion, the support of St is known because it identifies missing entries.Source: B. Our Contributions · p. 2
  • The analysis requires projection-PCA because its subspace-estimation error is correlated with Lt, unlike the independent or uncorrelated noise assumed in much finite-sample PCA work.The proof also draws on sparse-recovery results, eigenvector perturbation bounds, and matrix Hoeffding bounds.Source: B. Our Contributions · p. 2

D. High probability tail bounds for sums of independent random matrices

This material introduces probability tools for analyzing sums of independent random matrices and defines the recursive recovery problem as separating sparse signals from a changing low-dimensional component. The problem includes estimating both components over time, given an initial subspace estimate.

D. High probability tail bounds for sums of independent random matrices

  • A probability lemma transfers a conditional lower bound to a further conditioning event, while another invokes the chain rule for nested events.The nested-event sequence is described as contracting; the supplied passage does not include the lemma's full conclusion.Source: D. High probability tail bounds for… · p. 4
  • Matrix Hoeffding provides tail bounds for sums of independent random matrices, with corollaries covering conditional settings and nonzero-mean matrices.The supplied statements include a conditional Hermitian-matrix version and one for arbitrary matrices, though their full bounds are not shown.Source: D. High probability tail bounds for… · pp. 4–5

III. PROBLEM DEFINITION AND MODEL ASSUMPTIONS

  • The recovery problem models each measurement as a sparse vector plus a dense, low-dimensional component that changes over time.The initial training period has zero sparse signal, and an accurate estimate of the initial subspace is given.Source: A. Problem Definition · p. 5

A. Problem Definition

  • The objective is to estimate both components after training and periodically estimate the subspace containing the low-dimensional component.The subspace model allows changes at discrete times, while its projection variances may change continuously.Source: A. Problem Definition · p. 5
  • The stated subspace-change model adds new directions, so its rank can only grow; keeping dimension small therefore requires bounding the number of changes.A later model allows deletions, with a separation and clustering condition instead of a bound on the number of changes.Source: A. Problem Definition · p. 6

B. Slow subspace change

The analysis assumes sufficiently slow subspace changes and dense subspace directions, then gives high-probability guarantees for ReProCS under those and other conditions. It also notes that some assumptions depend on the algorithm's own estimates.

B. Slow subspace change

  • Slow subspace change requires long enough gaps between changes, gradual growth of projection onto newly added directions, and few new directions per change.The number of new directions is bounded by c_max, which is much smaller than r_0.Source: B. Slow subspace change · p. 6

C. Measuring denseness of a matrix and its relation with RIC

  • The denseness coefficient κ_s measures non-compressibility: small values indicate spread-out, dense entries, while larger values indicate compressibility.For a basis matrix, denseness is related to the restricted isometry constant of its orthogonal-complement projector.Source: C. Measuring denseness of a matrix and… · p. 6

A. Performance Guarantees

  • With high probability, ReProCS exactly recovers the sparse support at all times, bounds sparse recovery error by 0.18√(cγ_new) plus a constant times √ζ, and reduces subspace error below 0.01√ζ within K projection-PCA steps.These guarantees require an accurate initial subspace estimate, appropriate parameters, slow subspace change, denseness, and other stated assumptions.Source: A. Performance Guarantees · pp. 7–8
  • The error in recovering both the sparse and low-dimensional components decays with each projection-PCA step, with high probability.The passage says the two errors decay in a similar fashion.Source: A. Performance Guarantees · p. 8
  • The guarantee's most important limitation is its dependence on denseness assumptions for D_new,k and Q_new,k, which depend on algorithm estimates.The analyzed algorithm also requires knowledge of model parameters.Source: A. Performance Guarantees · p. 8

B. Projection-PCA algorithm for ReProCS

Projection-PCA removes an estimated low-dimensional subspace before applying PCA, while ReProCS uses projected sparse recovery to estimate the sparse signal and iteratively update that subspace. The discussion identifies parameter and model assumptions that constrain its guarantees.

B. Projection-PCA algorithm for ReProCS

  • Projection-PCA applies PCA to data projected perpendicular to a basis, estimating the leading r eigenvectors from the projected covariance.This differs from standard PCA, which applies PCA directly to the data matrix.Source: B. Projection-PCA algorithm for ReProCS · p. 8

C. Recursive Projected CS (ReProCS)

  • ReProCS projects each measurement away from the estimated subspace, recovers the sparse vector by ℓ1 minimization, thresholds its support, and refines the estimate by least squares.The remaining signal is used to estimate the low-rank component and update the subspace using K projection-PCA steps.Source: C. Recursive Projected CS (ReProCS) · pp. 8–9
  • Each projection-PCA update reduces projected noise and reconstruction error when new-subspace energy increases slowly; after K updates, both errors are bounded by a constant times √ζ.The smaller reconstruction error also reduces perturbation in the next projection-PCA step.Source: C. Recursive Projected CS (ReProCS) · p. 9

D. Discussion

  • Smaller target error ζ requires longer projection-PCA intervals, more updates, and larger delays between subspace changes.The interval length α and update count K increase as ζ decreases.Source: D. Discussion · p. 10
  • The guarantees require slow subspace changes, dense subspaces, and bounds on sparsity and rank; the online sparsity-rank product restriction is stronger than the cited PCP condition.The authors explain that per-time sparse recovery does not exploit the low-dimensional structure of the new, unestimated subspace.Source: D. Discussion · p. 10
  • Algorithm 2 assumes model parameters, including the number of new directions, a bound on their initial coefficient size, and subspace-change times, the last being most restrictive.A practical version with parameter-setting heuristics is cited as [26].Source: D. Discussion · pp. 10–11

V. DEFINITIONS NEEDED FOR PROVING THEOREM 4.2

  • The proof defines interval-specific projection and subspace quantities, along with events tracking exact support recovery and bounds on subspace error.These definitions organize the conditions used to establish the theorem's guarantees.Source: §V · pp. 11–12

VI. PROOF OF THEOREM 4.2

The proof establishes the theorem by bounding subspace error across projection-PCA updates and showing that successful recovery in one interval implies success in the next with high probability. Together, these results yield the stated guarantees with probability at least 1 − n^-10.

VI. PROOF OF THEOREM 4.2

  • If recovery and subspace estimation succeed in one interval, the proof shows they also succeed in the next interval with high probability.The argument propagates the good-event condition across intervals and then across subspace changes.Source: A. Two Main Lemmas and Proof of… · pp. 12–13
  • ζ+_k ≤ 0.6^k + 0.4cζ bounds subspace error across projection-PCA updates, giving an exponentially decaying upper bound.The bound applies for k = 1, 2, …, K under the theorem's assumptions.Source: A. Two Main Lemmas and Proof of… · pp. 12–13
  • 1 − n^-10 is the stated lower bound on the probability that all theorem conclusions hold.The proof combines the per-update probability bound pK(α, ζ) across K updates and J subspace changes.Source: A. Two Main Lemmas and Proof of… · p. 13

B. Proof of Lemma 6.1

The proof bounds the subspace-error sequence across projection-PCA steps, then uses conditional guarantees for projected sparse recovery and subspace updates to establish interval-by-interval success.

B. Proof of Lemma 6.1

  • Using the same upper bounds as before, the proof shows that the denominator is at least 0.78 and therefore remains strictly positive under those bounds.Source: B. Proof of Lemma 6.1 · p. 13

C. Proof of Lemma 6.2

  • Conditioned on the previous interval's good event, projected CS exactly recovers support and bounds reconstruction error under Theorem 4.2's assumptions.The CS estimate error is bounded by 7ξ0, and the support threshold conditions yield exact support recovery.Source: C. Proof of Lemma 6.2 · p. 14
  • The next interval's good event follows by combining the projected-CS and projection-PCA lemmas with the event-propagation bound.The proof of the projection-PCA lemma uses perturbation bounds and matrix Hoeffding inequalities.Source: C. Proof of Lemma 6.2 · p. 14

D. Proof of Lemma 6.4

The proof of Lemma 6.4 derives projected-CS recovery guarantees, including exact support recovery under a suitable threshold. Lemma 6.5 then bounds projection-PCA subspace error using eigenvector perturbation and concentration arguments.

D. Proof of Lemma 6.4

  • The projected-CS matrix's restricted isometry is bounded using subspace denseness and subspace-estimation error.The proof bounds δs(Φ0) by a quantity below 0.1 under its stated conditions.Source: D. Proof of Lemma 6.4 · p. 14
  • When the prior interval is good, projected CS has bounded estimate error and exactly recovers support under the theorem's threshold conditions.The proof uses the noise bound and requires Smin > 14ξ0 with 7ξ0 ≤ ω ≤ Smin − 7ξ0.Source: D. Proof of Lemma 6.4 · p. 15

E. Proof of Lemma 6.5

  • The projection-PCA error bound follows from eigenvalue separation and the sin θ theorem, with perturbation terms bounded by matrix Hoeffding inequalities.The proof also bounds the denseness of the unestimated new subspace before bounding the subspace-error terms.Source: E. Proof of Lemma 6.5 · pp. 15–16

VII. REPROCS WITH CLUSTER PCA

ReProCS-cPCA extends ReProCS to subspace models with additions and deletions, using clustered covariance eigenvalues to re-estimate the subspace. Under its assumptions, it guarantees exact support recovery and bounded reconstruction error, without requiring a bound on the number of changes when change-point spacing grows logarithmically with that number.

VII. REPROCS WITH CLUSTER PCA

  • The subspace model permits both added and deleted directions while bounding the cumulative difference between their counts, so the true subspace rank remains bounded.At each change time, new directions are orthogonal to the previous subspace, while retained directions may be rotated.Source: §VII · p. 16
  • Re-estimating the current subspace after estimating new directions allows deletion of old directions and removes the need to bound J if change-point spacing grows logarithmically with J.The original addition-only algorithm's estimated rank keeps increasing even when the true rank is bounded.Source: §VII · p. 16

A. Clustering assumption

  • The clustering assumption requires covariance eigenvalues to be stable or nearly stable after a settling period and grouped into clusters with small within-cluster spread and large inter-cluster gaps.New-direction variances may grow during the initial Kα frames before the clustering period begins.Source: A. Clustering assumption · pp. 16–17

B. The ReProCS with Cluster PCA Algorithm

  • After subspace changes, ReProCS-cPCA recovers the current subspace one eigenvalue cluster at a time, using standard PCA for the first cluster and projection-PCA for later clusters.It updates the estimated subspace after all clusters are recovered; the change intervals must accommodate the addition and cluster-estimation steps.Source: B. The ReProCS with Cluster PCA… · p. 17

C. Performance Guarantees

  • With probability at least 1 − 2n^-10, ReProCS-cPCA exactly recovers Tt and bounds ∥et∥2 by 0.18√cγnew + 1.24√ζ at all times.The theorem also gives phase-dependent bounds on subspace error and reconstruction error.Source: C. Performance Guarantees · p. 19

D. Special Case when f is small

When the covariance condition number is small, the clustering assumption is unnecessary. The discussion contrasts ReProCS-cPCA with ReProCS and PCP, noting its change-count advantage alongside stronger assumptions and model-parameter requirements.

D. Special Case when f is small

E. Discussion

  • Smaller target error ζ requires longer addition and deletion PCA intervals, more addition updates, and therefore longer spacing between subspace changes.K increases as ζ decreases, while αadd(ζ) and αdel(ζ) are inversely proportional to ζ.Source: E. Discussion · p. 19
  • Compared with ReProCS, ReProCS-cPCA requires a condition on each current subspace rather than the concatenated new directions, and its ζ bound depends on rmax + cmax rather than J.The cluster sizes can be estimated by clustering eigenvalues of an estimated covariance matrix.Source: E. Discussion · p. 19
  • ReProCS-cPCA avoids a bound on J when subspace-change spacing grows in proportion to log J, but requires clustered eigenvalues, longer spacing, and knowledge of model parameters.The paper identifies dependence on algorithm-estimate assumptions and knowledge of subspace-change times as limitations.Source: E. Discussion · p. 19

VIII. PROOF OF THEOREM 7.7

  • The proof section introduces definitions, develops key lemmas, and then proves Theorem 7.7.Source: §VIII · p. 20

Define the sets

The proof combines bounds for the addition and cluster-PCA deletion steps, then accumulates their success probabilities across subspace changes. Under Theorem 7.7's conditions, this yields its high-probability recovery, reconstruction-error, and subspace-error conclusions.

B. Two Main Lemmas

  • The addition step contracts the subspace-error bound across K updates, with ζ+_k ≤ 0.6^k + 0.4cζ, and gives conditional success probability at least pK(α, ζ).The result holds under Theorem 7.7's conditions and a positive probability for the preceding success event.Source: B. Two Main Lemmas · p. 21
  • Each cluster-PCA deletion iteration succeeds with conditional probability at least p̃(α̃, ζ), and the lemma also bounds the probability of reaching the next interval's success event.Source: B. Two Main Lemmas · p. 21

C. Proof of Theorem 7.7

  • Combining the stepwise bounds gives Theorem 7.7's conclusions with probability at least 1 − 2n^-10.The proof links success across J changes to bounds on support recovery, reconstruction error, and subspace error.Source: C. Proof of Theorem 7.7 · p. 22

D. A lemma needed for getting high probability bounds on the subspace error

  • The cluster-PCA subspace-error bound follows when the estimated cluster covariance has a positive eigenvalue gap after accounting for the perturbation term.The high-probability lemma bounds the relevant covariance terms and then bounds the cluster subspace error.Source: E. Bounding the subspace error, ˜ζk · p. 22

IX. MODEL VERIFICATION AND SIMULATION EXPERIMENTS

The section checks whether real background sequences exhibit the assumed slow subspace changes and clustered eigenvalues, then tests ReProCS variants in simulations. It closes by stating the guarantees and assumptions of the analyzed approach.

A. Model Verification for real data

  • The curtains and lake sequences retained 90% of their energy in 34 and 14 directions, respectively, after projection into the retained eigenspaces.The original sequences were approximately low rank rather than exactly low rank.Source: A. Model Verification for real data · p. 23
  • For α=40, new-direction projections during the initial frames were 0.125γ* for curtains and 0.06γ* for the lake, and increased slowly.The reported bound held with v=1.5 for curtains and v=1.8 for the lake.Source: A. Model Verification for real data · p. 23
  • The lake-video clustering check found that the clustering assumption held, with ˜gmax = 7.2, ˜hmax = 0.34, and ϑmax = 7.Because one sequence cannot estimate Λt directly, the check assumed Λt remained the same long enough for estimation by a time average.Source: A. Model Verification for real data · p. 23

B. Simulation Experiments

  • The simulations generated a 2048 × 4200 measurement matrix as the sum of sparse St and low-rank Lt, with correlated support changes in one experiment.As Δ increased in that experiment, St’s rank decreased.Source: B. Simulation Experiments · p. 23
  • For Δ=2 and Δ=10, ReProCS’s subspace error decreased exponentially and stabilized after about four projection-PCA updates, more slowly for Δ=10.For Δ=100, the subspace error decayed slowly and did not return to .01 within Kα frames; when the reported ratio was 1, subspace and reconstruction errors did not decrease from their initial values.Source: B. Simulation Experiments · p. 24
  • ReProCS and ReProCS-cPCA errors decreased exponentially and stabilized; ReProCS-cPCA outperformed ReProCS when deletion steps were performed.Figure 8 compares normalized sparse-recovery errors for r0 = 36 and s = 20, with PCP runs marked by red triangles.Source: Figure 8 · p. 24, B. Simulation Experiments · p. 25

X. CONCLUSIONS AND FUTURE WORK

  • ReProCS assumes a known subspace-change model and a dense currently unestimated subspace; w.h.p., it exactly recovers St’s support and bounds both reconstruction errors by a time-invariant small value.After each subspace change, the subspace recovery error is also guaranteed to decay to a sufficiently small value within finite delay.Source: §X · p. 25

APPENDIX A PROOFS OF PRELIMINARY LEMMAS

The appendix establishes preliminary subspace and probability bounds, then explains why projection-PCA is preferable to standard PCA when estimation errors are correlated with the data.

APPENDIX A PROOFS OF PRELIMINARY LEMMAS

  • The preliminary subspace arguments relate projector distance and cross-subspace singular values to the estimated subspace error ζ∗.The proof compares projector differences and bounds singular values after projection using ζ∗.Source: Appendix A · pp. 25–26
  • The probability lemmas center conditionally independent matrix variables and apply concentration bounds under the stated conditional bounds.The proof fragments use conditional expectations and matrix dilation to apply the stated inequalities.Source: Appendix A · pp. 26–27

A. Projection-PCA vs Standard PCA

  • Because estimation error is correlated with L_t, standard PCA can yield a meaningless subspace-error bound; projection reduces the perturbation and its bound.The comparison concerns the setting where L_t may be large and its covariance condition number cannot be assumed small.Source: A. Projection-PCA vs Standard PCA · p. 27
  • Projection-PCA bounds total subspace error by the sum of existing- and new-subspace errors, whereas standard PCA’s bound need not decrease across updates.This supports showing that projection-PCA’s subspace error decays after a change.Source: A. Projection-PCA vs Standard PCA · p. 27

B. Why not use all kα frames at t = tj + kα −1

The authors consider using all kα past estimates for projection-PCA, which may improve the algorithm but makes its analysis more involved.

B. Why not use all kα frames at t = t_j + kα −1

  • Using the past kα estimates at the kth projection-PCA update is proposed as a possible alternative implementation.The authors believe it may improve the algorithm and may be analyzable with this paper’s approach.Source: B. Why not use all kα frames at t = tj… · p. 27
  • With this alternative, the perturbation H_k combines contributions from past terms rather than being approximately just the latest term.The perturbation is described as an average involving past projected estimates.Source: B. Why not use all kα frames at t = tj… · p. 27
  • Bounding those terms involves different probabilities, making a proof analogous to Lemma 6.11 more complicated.The passage presents this as the reason the variant’s analysis is more involved.Source: B. Why not use all kα frames at t = tj… · pp. 27–28

APPENDIX C PROOF OF LEMMA 6.11

The appendix proves Lemma 6.11 by conditioning on the prior estimate state, bounding matrix terms, and applying concentration inequalities.

APPENDIX C PROOF OF LEMMA 6.11

  • Conditioned on X_{j,k−1}, the proof treats the relevant summands as independent on the stated event Γ_{j,k−1}.The argument uses independence of the a_t variables and represents terms as functions of the conditioned state and a_t.Source: Appendix C · p. 28
  • Hoeffding corollaries provide high-probability bounds for the component terms used in the proof.The passage states that the resulting probability is lower bounded by 1−p_c(α, ζ).Source: Appendix C · pp. 29–30
  • The proof bounds matrix terms under that conditioning and combines probability bounds with a union bound to establish the lemma’s claims.It then applies Lemma 2.11 to obtain the stated claims.Source: Appendix C · pp. 28, 30

APPENDIX D PROOF OF LEMMA 8.15

The appendix proves Lemma 8.15 by controlling errors in estimated subspaces and the singular values of projected directions.

APPENDIX D PROOF OF LEMMA 8.15

  • The projection error for the detected subspace directions is bounded by rζ.The proof uses the triangle inequality and mutual orthogonality of the estimated directions.Source: Appendix D · p. 30
  • The singular values of the projected directions lie between 1−r²ζ² and 1.The proof derives this bound using the QR decomposition and a preliminary subspace lemma.Source: Appendix D · p. 30
  • The proof also bounds overlap between the estimated detected subspace and the undetected directions using rζ.It applies preliminary subspace bounds to the undetected directions and G_k.Source: Appendix D · p. 30

APPENDIX E PROOF OF LEMMA 8.19

The proof conditions on a good history and bounds matrix terms using conditional independence and Hoeffding corollaries. It combines these bounds with union bounds to establish the lemma’s claims.

APPENDIX E PROOF OF LEMMA 8.19

  • Conditioned on the good history, the summands are mutually independent, allowing concentration bounds to be applied to their sums.The proof identifies this conditional independence for terms involving both the sparse coefficients and the reconstruction errors.Source: Appendix E · pp. 30–31
  • Combining bounds (25)–(27) with a union bound gives a high-probability lower bound on the minimum eigenvalue of ˜A_k.The argument then applies Lemma 2.11 to extend the conditional result.Source: Appendix E · p. 31
  • The proof controls terms in the third claim by expressing ˜H_k as a difference and bounding the resulting error-dependent matrices.It uses Hoeffding corollaries and a union bound to combine the termwise estimates.Source: Appendix E · pp. 31–32
  • For the matrix terms, the proof establishes conditional bounds on their norms and expectations before applying the Hoeffding corollaries.For example, it bounds one term using b1 = φ+2ζ and b3 := √rζφ+γ∗.Source: Appendix E · p. 32
Loading 1211.3754v10…