PaperlayerView exact revision on arXiv

Source-linked AI summary

An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum

Han Guo, Chenlu Qiu, Namrata Vaswani

arXiv:1310.4261v3cs.ITmath.IT

TL;DR

Recovering sparse signals alongside dense sequences in slowly changing low-dimensional subspaces is difficult when the dense component may be large, as in video foreground-background separation. The paper develops and evaluates Prac-ReProCS, including a compressive version. It reports strong results on simulated data and video, outperforming many recent state-of-the-art algorithms.

  • Problem

    The task is to recover sparse and dense sequences from their sum when the dense sequence lies in a slowly changing low-dimensional subspace, including settings such as video layering.

    Source: §I · p. 1

  • Method

    Prac-ReProCS is a practically usable modification of ReProCS, and the paper also proposes a compressive version for measurements of the form M_t = A S_t + B L_t.

    Source: §I · pp. 1–2

  • Results

    Prac-ReProCS performs well on simulated data and real video, with performance better than many recent state-of-the-art algorithms.

    Source: §VII · p. 13

  • Takeaways & Limitations

    The paper reports that most assumptions used for its guarantees are valid for real videos and evaluates the approach for compressive recovery as well.

    Source: §VII · p. 13

    The detailed analysis assumes immediately detected subspace-change times and projection-PCA estimates satisfying a specified error bound.

    Source: A. Detailed Discussion of Why ReProCS… · p. 13

Abstract

from arXiv · show

This paper designs and evaluates a practical algorithm, called practical recursive projected compressive sensing (Prac-ReProCS), for recovering a time sequence of sparse vectors $S_t$ and a time sequence of dense vectors $L_t$ from their sum, $M_t:= S_t + L_t$, when any subsequence of the $L_t$'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 a practical modification of its theoretical counterpart which was analyzed in our recent work. Experimental comparisons demonstrating the advantage of the approach for both simulated and real videos are shown. Extension to the undersampled case is also developed.

I. INTRODUCTION

The paper targets online recovery of sparse and low-dimensional components when the low-dimensional sequence lies in a slowly changing subspace, motivated by separating moving foreground from video background. It presents a practical ReProCS modification, with experiments addressing correlated support changes and small-magnitude sparse signals.

I. INTRODUCTION

  • Video layering separates moving foreground regions from a slowly changing background; foreground and background are useful for tracking or surveillance and background editing, respectively.The model also covers compressive video, fMRI, and sensor-network event detection.Source: §I · p. 1
  • Robust PCA addresses outlier-corrupted data, with sparse vectors serving as an outlier model; batch PCP separates sparse and low-rank matrices from their sum.PCA itself finds a low-dimensional subspace minimizing projection mean-squared error for a given dimension.Source: §I · pp. 1–2
  • Online recovery avoids the delay, speed, and memory costs of batch processing, while ReProCS addresses foreground supports that are not independent over time.Earlier guarantees require denseness, slow subspace change, and some support change at least every h frames.Source: §I · p. 2
  • Prac-ReProCS is reported more robust to correlated support changes than PCP and other existing methods, and better at recovering small-magnitude sparse vectors than recursive and batch alternatives.The paper also develops a compressive version for measurements M_t = A S_t + B L_t.Source: §I · p. 2

A. Notation

  • The notation defines a basis matrix by orthonormal columns and uses support and index-set operations to describe sparse vectors and their coordinates.It also defines singular-value-based approximate bases and the restricted isometry constant.Source: A. Notation · pp. 2–3

II. PROBLEM DEFINITION AND ASSUMPTIONS

The problem is to recursively estimate sparse and dense components, and the subspace containing the dense sequence, from measurements. Its assumptions include an initial background-only training sequence and permit the dense component to be as large as or larger than the sparse one.

II. PROBLEM DEFINITION AND ASSUMPTIONS

  • After an initial sparse-free training sequence estimates the dense-component subspace, each new measurement is used with the previous estimates and subspace estimate to recover both components recursively.In video, the components correspond to foreground and background; mean subtraction makes the model M_t = S_t + L_t.Source: §II · p. 3
  • The dense component may have entries smaller than, comparable to, or larger than the nonzero sparse entries; when it is the noise, comparable or greater norm makes recovery difficult.The model also identifies sparse fMRI active regions against a background brain image.Source: §II · p. 3
  • A batch robust-PCA method can initialize the subspace if no sparse-free training sequence is available, provided that the initial data meet that method’s assumptions.This is an alternative to the paper’s assumed background-only training sequence.Source: §II · p. 3

A. Slowly changing low-dimensional subspace change

The dense sequence is modeled as low-dimensional over sufficiently long windows, with its subspace either fixed or changing gradually. A piecewise-constant basis model formalizes this assumption and accommodates gradual growth in new directions after a change.

A. Slowly changing low-dimensional subspace change

  • For sufficiently long windows, the dense sequence lies in a subspace whose dimension is much smaller than the window length and ambient dimension, and the subspace is fixed or slowly changing.The piecewise-constant change model is a simplified representation of typical practice.Source: A. Slowly changing low-dimensional… · p. 3
  • The model represents L_t as P_t a_t, with a low-dimensional basis P_t held piecewise constant between change times and updated by adding new directions and rotating the basis.Bounds on new directions, change intervals, and total changes keep the modeled dimension small relative to the ambient dimension.Source: A. Slowly changing low-dimensional… · p. 3
  • Slow change means the component outside the previous subspace starts small after a change and grows gradually; the specific growth model is not required.Background sequences are modeled this way except around camera-viewpoint or scene changes, and the paper says it verifies the assumption in Section V.Source: A. Slowly changing low-dimensional… · pp. 3–4

B. Denseness

Denseness is assumed so projection away from the low-dimensional subspace preserves sparse-recovery properties. The sparse sequence is also assumed to have limited support size and to change often enough to expose some background.

B. Denseness

  • The denseness condition makes the restricted isometry constant of the projection I − P P′ small, supporting recovery of sparse vectors from projected measurements.The paper assumes a tighter denseness bound for newly added subspace directions.Source: B. Denseness · p. 4
  • The model constrains sparse support size and support changes, with either small changes or a tighter support-size bound when changes are large.It also requires some support change at least once every h frames so that background behind the foreground is visible for estimating subspace changes.Source: C. Small support size, some support… · p. 4
  • Video foregrounds are typically sparse moving regions, while lighting, water, or leaves can produce global background changes consistent with a dense background subspace.The paper states that it verifies these assumptions on real video data.Source: C. Small support size, some support… · p. 4, B. Denseness · p. 4

III. PRAC-REPROCS: PRACTICAL REPROCS

Prac-ReProCS projects measurements away from the estimated low-dimensional subspace before recovering the sparse component, then updates that subspace through practical projection PCA. Its subspace-change detector avoids requiring known change times or numbers of new directions.

A. Basic algorithm

  • Slow subspace change makes the projected low-rank contribution small, turning sparse recovery into a noisy compressive-sensing problem solved with ℓ1 minimization.The method uses the previous subspace estimate for projection and sets the recovery constraint using an estimate of the projected noise.Source: A. Basic algorithm · p. 5
  • Projection PCA adds new directions in batches, repeatedly updating the subspace estimate until its error is sufficiently small.Each update projects recent low-rank estimates off the previous basis and computes leading left singular vectors.Source: A. Basic algorithm · p. 5
  • Prac-ReProCS detects subspace changes by thresholding singular values of recent projected estimates, then estimates new directions without known change times or direction counts.It uses a training-set singular-value threshold and clips the estimated number of new directions at ⌈α/3⌉.Source: A. Basic algorithm · p. 5
  • Under the stated assumptions and theoretically motivated parameters, the method is shown to recover the sparse support exactly and the low-rank subspace accurately within finite delay, with high probability.The paper gives a brief proof overview in its appendix.Source: A. Basic algorithm · p. 5
  • Because projection PCA only adds directions, deleting directions that have left the subspace may provide more effective measurements for sparse recovery, though this did not help much experimentally.The paper also describes incremental SVD for recursive updates, but reports no speedup in practice with α = 20.Source: A. Basic algorithm · p. 5

B. Exploiting slow support change when valid

When support changes slowly, the previous support estimate can guide sparse recovery, but its usefulness depends on how accurately it predicts the current support. Prac-ReProCS uses weighted ℓ1 recovery and support refinement, switching to simple ℓ1 when the slow-change condition is not met.

B. Exploiting slow support change when valid

  • The experiments use α = 20, Kmin = 3, and Kmax = 10, with b and q selected according to whether the data are approximately low-rank and the sparse component’s magnitude.The listed settings distinguish simulated data from real videos and the lake video.Source: B. Exploiting slow support change when… · p. 6
  • After sparse recovery, it retains the largest-magnitude candidate entries, computes a least-squares estimate on them, thresholds that estimate, and refits on the resulting support.The algorithm’s steps specify pruning to 1.4 times the previous support size before thresholding.Source: B. Exploiting slow support change when… · p. 6
  • When support changes slowly, weighted ℓ1 recovery can exploit the previous support estimate; if that estimate is not a good predictor, the method instead uses simple ℓ1.The paper states weighted ℓ1 is better when the support estimate contains at least 50% correct entries.Source: B. Exploiting slow support change when… · p. 6
  • The algorithm estimates whether the previous support is sufficiently accurate and uses weighted recovery when the estimated correct fraction exceeds 0.5, otherwise setting λ = 1.The estimate is based on the overlap of consecutive support estimates.Source: B. Exploiting slow support change when… · p. 6

C. Improved support estimation

The support-estimation refinement uses a least-squares step to reduce bias, then thresholds the refined estimate to remove extras and control support growth.

C. Improved support estimation

  • The Add-LS-Del procedure keeps the k largest-magnitude entries from the sparse estimate and computes least squares on that candidate support, reducing bias relative to the initial estimate.The method sets k = 1.4 times the previous support size to allow modest support growth and improve detection of new elements.Source: C. Improved support estimation · pp. 6–7
  • Thresholding the refined estimate removes extra support entries and helps keep the estimated support from growing unless the object itself grows.A final least-squares estimate is then computed on the thresholded support.Source: C. Improved support estimation · p. 7
  • In the recursive SVD update, the basis and singular values are updated from the QR/SVD factors, but frequent updates can cause loss of orthogonality.Modified Gram–Schmidt reorthonormalization can address this numerical issue.Source: C. Improved support estimation · p. 7

D. Simplifying subspace update: simple recursive PCA

The paper considers replacing projection PCA with recursive PCA, while addressing the growing cost of repeated batch PCA through incremental SVD and periodic rank truncation.

D. Simplifying subspace update: simple recursive PCA

  • Computing PCA from all past low-rank estimates becomes increasingly costly over time, while using only a recent window still requires a large window for accuracy.This motivates the recursive PCA alternative.Source: D. Simplifying subspace update: simple… · p. 7
  • The recursive PCA update can bias estimates toward zero on the complement of the previous support, making new support values smaller than their true values.The supplied passage attributes this bias to the ∥x(ˆTt−1)∥1 term.Source: D. Simplifying subspace update: simple… · p. 7
  • The proposed alternative uses incremental SVD and truncates the estimated basis to rank ˆr every d frames.The algorithm applies the same projection, sparse-recovery, and low-rank-estimation steps before updating the subspace estimate.Source: D. Simplifying subspace update: simple… · p. 7

IV. COMPRESSIVE MEASUREMENTS: RECOVERING St

For undersampled measurements, the paper projects out an estimated background subspace to recover the sparse component, then uses the recovered component to estimate the background. Recovery relies on assumptions about the measurement matrix and subspace incoherence, and recovering the background itself has an additional constraint.

IV. COMPRESSIVE MEASUREMENTS: RECOVERING St

  • The compressive case assumes a restricted isometry property for A and low incoherence between the background subspaces and sets of columns of A.It also assumes an initial training sequence containing only BLt.Source: §IV · p. 7
  • The method recovers St at each time, but cannot recover Lt unless B varies over time.The passage identifies B = A in undersampled fMRI and single-pixel imaging, and B = I for low-dimensional sensor noise.Source: §IV · p. 8
  • Projecting out the estimated background subspace yields measurements for sparse recovery; subtracting the recovered sparse component then estimates the transformed background for subspace updates.The method starts with an initial background-only training sequence to estimate the subspace basis.Source: §IV · p. 8
  • RIP and subspace incoherence ensure recovery of sparse vectors by ℓ1 minimization; extending the argument to estimated subspaces and small noise requires more work.The paper says those extensions can be developed, citing [45].Source: §IV · p. 8

V. MODEL VERIFICATION

The authors test whether lake-water and curtain backgrounds meet the low-dimensional and slow-change assumptions, and examine foreground support behavior in the curtain sequence.

A. Low-dimensional and slow subspace change assumption

  • 95% of background energy lies in at most 38 curtain or 33 lake directions, while post-change residuals start small for 100–150 frames and then grow gradually.The analysis uses un-low-rankified data and approximate background bases computed over 725-frame intervals.Source: A. Low-dimensional and slow subspace… · p. 8

B. Denseness assumption

  • Exact denseness verification is infeasible because computing κs(.) is exponential, so the authors inspect overlap with the true or estimated support as a proxy.For the curtain video, the proxy is an estimated support from frames 35–80 featuring a person in a black shirt against white curtains.Source: B. Denseness assumption · p. 8

C. Support size, support change and slow support change

  • The curtain foreground occupies at most 10.2% of the image; support changes occur at least every three frames, and no more than 9.9% of the support changes at once.The support-change behavior exposes background behind the foreground.Source: C. Support size, support change and… · p. 9

VI. SIMULATION AND EXPERIMENTAL RESULTS

Across simulated and real videos, ReProCS recovers sparse foregrounds and low-dimensional backgrounds more successfully than the compared methods in several challenging settings. The experiments also compare its speed and test its extension to compressive measurements.

Simulated Data

  • ReProCS recovers both small-magnitude and fairly large-support sparse components better overall than the compared methods; iRSL performs very poorly in both cases.RSL, PCP, and GRASTA work to some extent in certain cases, but not as well as ReProCS.Source: §VI · p. 9, Table I · p. 11

Partly Simulated Video

  • In partly simulated video, PCP has large error and GRASTA fails, while RSL recovers many extra pixels; ReProCS performs better than RSL.The simulated foreground moves in a correlated fashion, and its magnitude is roughly equal to or smaller than the background magnitude.Source: §VI · p. 10, Figure 2 · p. 11

Real Video Sequences

  • On the curtain video, ReProCS recovers backgrounds without the person that appears in other methods’ outputs; on the monitor video, it recovers the person in most frames, but all methods fail in the final white-on-white frames.The curtain sequence has similar shirt and curtain colors; the monitor sequence has a large foreground support and a white region on the screen.Source: §VI · p. 10, Figure 4 · p. 12, Figure 5 · p. 12

Time Comparisons

  • GRASTA is fastest and ReProCS second fastest; both recursive methods provide foreground and background recovery as each frame arrives, unlike batch PCP and RSL.The authors expect mex files for the subspace update step could speed up ReProCS.Source: §VI · p. 10, Table II · p. 11

Compressive ReProCS

  • For compressive measurements, ReProCS recovers the sparse component fairly accurately while SpaRCS does not work, though errors exceed those in the fully sampled case.The comparison uses Gaussian measurements with m = 0.7n; the authors note that the SpaRCS experiments in use slower-changing backgrounds and smaller foreground supports than their data.Source: §VI · p. 10, Figure 7 · p. 13

VII. CONCLUSIONS AND FUTURE WORK

The paper designs and evaluates Prac-ReProCS, a practical modification of ReProCS, and reports strong performance on simulated data and real video foreground–background separation. It also evaluates a compressive version, while noting a boundary for applying it to fMRI with changing measurement matrices.

VII. CONCLUSIONS AND FUTURE WORK

  • Prac-ReProCS performs excellently on simulated data and video foreground–background separation, outperforming many recent state-of-the-art algorithms.The authors also report that most assumptions used for its guarantees hold for real videos.Source: §VII · p. 13
  • The paper proposes and evaluates a compressive Prac-ReProCS algorithm.The authors say performance guarantees for compressive ReProCS remain ongoing work.Source: §VII · p. 13
  • The changing-measurement fMRI setting is outside the stated compressive algorithm’s scope because A_tL_t may not be low-dimensional.The authors note that replacing B = A with A_t in the algorithm does not apply for this reason.Source: §VII · p. 13

APPENDIX

The appendix explains why ReProCS can recover sparse and low-dimensional components as the subspace changes. Under stated assumptions, repeated projection PCA reduces the noise seen by sparse recovery, improving recovery and subspace estimates over successive updates.

A. Detailed Discussion of Why ReProCS Works

  • The subspace estimation error measure lies between zero and one; it is zero when the estimated subspace contains the true subspace and one when a true basis vector is orthogonal to the estimate.Source: A. Detailed Discussion of Why ReProCS… · p. 13
  • The argument assumes immediate detection of subspace changes, bounded low-rank vectors, at least Kα time between changes, gradual growth of new directions, and sufficiently accurate repeated projection PCA.It also assumes a small initial subspace estimation error; K is chosen so the new-subspace estimation error falls to the specified cζ bound.Source: A. Detailed Discussion of Why ReProCS… · p. 13
  • For the first interval after a subspace change, small subspace error and γ_new ≪ ∥S_t∥_2 keep projection noise small relative to the sparse signal.With an adequately large smallest nonzero entry, thresholding can recover the support exactly, after which least squares gives an accurate sparse estimate and supports accurate low-rank recovery.Source: A. Detailed Discussion of Why ReProCS… · p. 13
  • With each projection PCA step, the sparse-recovery noise is bounded by 0.72^(k−1)γ_new, and sparse and low-rank recovery errors decrease roughly exponentially with k.The appendix also says the projection PCA error decays roughly exponentially with k.Source: A. Detailed Discussion of Why ReProCS… · p. 13
  • After K projection PCA updates, the new-subspace error is bounded by cζ, yielding total subspace error at most r_jζ for the stated update.The appendix defines r_j = r_0 + jc and assumes this accumulated bound remains small.Source: A. Detailed Discussion of Why ReProCS… · pp. 13–14
Loading 1310.4261v3…