1

Incorporating Prior Information in Compressive
Online Robust Principal Component Analysis

arXiv:1701.06852v2 [cs.IT] 27 May 2017

Huynh Van Luong, Nikos Deligiannis, Jürgen Seiler, Søren Forchhammer, and André Kaup

Abstract—We consider an online version of the robust Principle
Component Analysis (PCA), which arises naturally in timevarying source separations such as video foreground-background
separation. This paper proposes a compressive online robust PCA
with prior information for recursively separating a sequences of
frames into sparse and low-rank components from a small set
of measurements. In contrast to conventional batch-based PCA,
which processes all the frames directly, the proposed method
processes measurements taken from each frame. Moreover, this
method can efficiently incorporate multiple prior information,
namely previous reconstructed frames, to improve the separation
and thereafter, update the prior information for the next frame.
We utilize multiple prior information by solving n-`1 minimization for incorporating the previous sparse components and using
incremental singular value decomposition (SVD) for exploiting
the previous low-rank components. We also establish theoretical
bounds on the number of measurements required to guarantee
successful separation under assumptions of static or slowlychanging low-rank components. Using numerical experiments,
we evaluate our bounds and the performance of the proposed
algorithm. In addition, we apply the proposed algorithm to online
video foreground and background separation from compressive
measurements. Experimental results show that the proposed
method outperforms the existing methods.
Index Terms—Prior information, compressed sensing, sparse
signal, n-`1 minimization, compressive measurements.

where k · k∗ is the matrix nuclear norm (sum of singular
values). For example, in video separation, a video sequence
is separated into slowly-changing background as the low-rank
term L and foreground as the sparse term S, which is the
quantity of interest in this paper. However, RPCA methods
[1]–[3] need to access all data frames, e.g., all frames of a
video, which is batch-based and not practical.
Problem. We consider a version of RPCA for the recursive
separation problem of a time-varying sequence of frames that
processes one frame per time instance and works on a small
set of measurements to separate large-scale data. In more
detail, we introduce a time instance t, at which we have
observed M t = Lt + S t , where S t = [x1 x1 ... xt ] and
Lt = [v 1 v 2 ... v t ], where [·] denotes a matrix and xt , v t ∈ Rn
are a column component in S t and Lt , respectively. In this
work, we consider compressive measurements of the observed
xt + v t at a time t, i.e., we observe y t = Φ(xt + v t ), where
Φ ∈ Rm×n (m < n) is a random projection [4], [5], and
that Lt−1 and S t−1 have been given for time instance t − 1.
Following Problem (1), we want to solve a problem at time t
as follows
min [Lt−1 v t ]

xt ,v t

I. I NTRODUCTION

P

RINCIPAL Component Analysis (PCA) is widely used
in statistical data analysis in a number of applications.
A modified version of Principal Component Analysis (PCA),
namely, robust PCA (RPCA) [1]–[3], is a well-known tool to
efficiently capture properties of signals of interest. A potential
application of RPCA is video foreground and background
separation, e.g., in video surveillance and online tracking brain
activation from MRI sequences. The goal of RPCA is to
decompose the high-dimensional matrix M into the sum of
unknown sparse S and low-rank L components. Principal
Component Pursuit (PCP) [1] recovers L and S by solving
the following program:
min kLk∗ + λkSk1 subject to L + S = M ,
L,S

(1)

H. V. Luong, J. Seiler, and A. Kaup are with the Chair of Multimedia Communications and Signal Processing, Friedrich-Alexander-Universität
Erlangen-Nürnberg, 91058 Erlangen, Germany (e-mail: huynh.luong@fau.de,
juergen.seiler@fau.de, and andre.kaup@fau.de).
N. Deligiannis is with the Department of Electronics and Informatics,
Vrije Universiteit Brussel, 1050 Brussels, and also with iMinds, 9050 Ghent,
Belgium (e-mail: ndeligia@etro.vub.ac.be).
S. Forchhammer is with the Department of Photonics Engineering, Technical University of Denmark, 2800 Lyngby, Denmark (e-mail:
sofo@fotonik.dtu.dk).

∗

+ λkxt k1 subject to y t = Φ(xt + v t ),

(2)
where Lt−1 = [v 1 v 2 ... v t−1 ] and S t−1 = [x1 x1 ... xt−1 ]
are given. We aim at solving Problem (2) given prior information Lt−1 , S t−1 , and Φ as formulated in Sec. II.
Related Works. Some previous approaches [6]–[9] were
proposed for online estimating low-dimensional subspaces
from randomly subsampled data. However, they have not
taken the sparse component xt into account. In addition,
compressive ReProCS in [10], [11] was proposed to recover
the sparse component for foreground extraction with compressive measurements. Compressive ReProCS [10] considers
recovering xt from y t = Φt (Axt + Bv t ) [10]. It can be
noted here that Φt ∈ Rn×n and A = B ∈ Rm×n . However,
the background v t is not recovered after each instance and no
explicit condition on how many measurements are required for
successful recovery is considered. In this work, we focus on
recovering both foreground and background components from
compressive measurements.
Recently, some related approaches to foreground extraction
in [12], [13] utilizing an adaptive rate of the compressive measurement were introduced, yet they considered the background
static. Another work in [14] proposed an incremental PCP
method that processes one frame at a time, however it did use
information of the full frame, rather than compressive measurements. Compressive PCP [15] considered the separation

2

on compressive measurements as a batch-based method.
Furthermore, the problem of reconstructing a time sequence
of sparse signals with prior information is also playing an
important role in the context of online RPCA [10], [11], [16].
There were several studies on sparse signal recovery with
prior information from low-dimensional measurements [10]–
[12], [16], [17]. The study in [17] provided a comprehensive
overview of the domain, reviewing a class of recursive algorithms for recovering a time sequence of sparse signals from a
small number of measurements. The studies in [10], [11], [16]
used modified-CS [18] to leverage prior knowledge under the
condition of slowly varying support and signal values. However, all the above can not exploit multiple prior information
gleaned from multiple previously recovered frames.
Contributions. We propose a compressive online RPCA
with multiple prior information named, CORPCA, which
exploits the information for previously recovered sparse components by utilizing RAMSIA [19] and leverages the slowlychanging characteristics of low-rank components via an incremental SVD [20]. We perform the separation in an online
manner by minimizing, (i) n-`1 function [19] for the sparse
part; and (ii) the rank of a matrix of the low-rank part.
Thereafter, the new recovered sparse and low-rank components
are updated as a new prior knowledge for the next processing
instance. Furthermore, we derive the number of measurements
that guarantee successful compressive separation. As such, we
set a bound on the number of required measurements based
on the current foreground-background and prior information.
The rest of this paper is organized as follows. Our problem
formulation and the proposed algorithm are presented in
Sec. II. We describe performance guarantees of the proposed
method including the measurement bound and the proof sketch
in Sec. III. We demonstrate numerical results of the proposed
method in Sec. IV.
II. P ROBLEM F ORMULATION AND A LGORITHM

instance t, we observe y t = Φ(xt + v t ) with y t ∈ Rm .
Let Z t−1 := {z 1 , ..., z J }, which is a set of z j ∈ Rn , and
B t−1 ∈ Rn×d denote prior information for xt and v t , respectively. We can form the prior information Z t−1 and B t−1
based on the reconstructed {x1 , ..., xt−1 } and {v 1 , ..., v t−1 },
which is discussed in Sec. II-B.
To solve the problem in (2), we fomulate the objective
function of CORPCA as
n
1
min H(xt , v t |y t , Z t−1 , B t−1 ) = kΦ(xt + v t ) − y t k22
xt ,v t
2
J
o
X
, (4)
+ λµ
βj kWj (xt − z j )k1 + µ [B t−1 v t ]
∗

j=0

where µ > 0. It can be seen that when v t is static, Problem
(4) would become Problem (3). When xt and v t are batch
variables without taking the prior information, Z t−1 and
B t−1 , and the projection Φ into account, Problem (4) becomes
Problem (1).
B. CORPCA Algorithm
We now describe how to solve Problem (4) and thereafter
update the prior information, Z t−1 and B t−1 , for the next
instance. First, we solve Problem (4) given Z t−1 and B t−1 .
Let
denote f (v t , xt ) = (1/2)kΦ(xt + v t ) − y t k22 , g(xt ) =
Pus
J
λ j=0 βj kWj (xt − z j )k1 , and h(v t ) = k[B t−1 v t ]k∗ . The
solution of (4) using proximal gradient methods [2], [21] gives
(k+1)
(k+1)
at iteration k + 1 can be iteratively
and v t
that xt
computed via the soft thresholding operator [21] for xt and
the single value thresholding operator [22] for v t :
 2o
n

(k) (k)
(k+1)
(k) 1
,
vt
=arg min µh(v t )+ v t− v t − ∇vt f (v t , xt )
2
2
vt
n

o
 2(5)
(k+1)
(k) 1
(k) (k)
xt
=arg min µg(xt )+ xt− xt − ∇xtf (v t , xt )
.
2
2
xt
(6)

In this section, we formulate explicitly our problem (in Sec.
II-A), following by our proposed algorithm in Sec. II-B.

The proposed CORPCA algorithm is described in Algorithm 1, where as suggested in [2], the convergence of
Algorithm 1 is determined by k∂H(xt , v t )|x(k+1) ,v(k+1) k22 <

A. Problem Formulation

2∗10−7 k(xt
is defined by:

The proposed CORPCA algorithm is based on RAMSIA
[19], our previously proposed agorithm that uses n-`1 minimization with adaptive weights to recover a sparse signal using
multiple side information signals. The objective function of
RAMSIA [19] is given by:
J
o
n
X
1
βj kWj (x−z j )k1 , (3)
min H(x) = kΦx−yk22 +λ
x
2
j=0

where λ > 0, βj > 0 are weights among side information
signals, and Wj is a diagonal weighting matrix for each
side information z j , Wj = diag(wj1 , wj2 , ..., wjn ), wherein
wji > 0 is the weight in Wj at index i for a given z j with
z 0 = 0.
The proposed CORPCA method aims at processing one
frame per time instance and incorporating prior information
for both sparse components and low-rank components. At time

(k+1)

(k+1)

, vt

t

t

)k22 and the proximal operator Γτ g1 (·)

n
o
1
Γτ g1 (X) = arg min τ g1 (V ) + ||V − X||22 .
2
V

(7)

Prior Information Update. Updating Z t and B t is carried
out after each time instance so as to be used for subsequent
processing. Because of the correlated characteristics of recursive frames, we can simply update prior information Z t by
the J latest previous xt , i.e., Z t := {z j = xt−J+j }Jj=1 .
For prior information B t ∈ Rn×d , we may have an adaptive update, where we can adjust the value d or keep a
constant number d of the columns of B t . For each time
instance, we use incremental singular decomposition SVD
[20], namely, incSVD(·) in Algorithm 1. When we update
B t = U t Γ µk g1 (Σt )V T
t , the dimension of B t is increased,
2
where B t ∈ Rn×(d+1) , after each instance. However, we need
to stay at a reasonable constant number of d, thus we update

3

Algorithm 1: The proposed CORPCA algorithm.
Input: y t , Φ, Z t−1 , B t−1 ;
Output: xt , v t , Z t , B t ;
// Initialization.
(−1)
(0)
(−1)
(0)
xt
= xt = 0; v t
= v t = 0; ξ−1 = ξ0 = 1;
µ0 = 0; µ̄ > 0; λ > 0; 0 <  < 1; k = 0; g1 (·) = k · k1 ;
while not converged do
// Solving the problem.
(k)
(k−1)
(k)
−1
(v t − v t
);
vet (k) = v t + ξk−1
ξk
(k)
(k−1)
ξk−1 −1
(xt − xt
);
ξk
(k)
(k)
(k)
(k)
ft ) = ∇xt f (v
ft )
∇vt f(vet , x
et , x
(k)
ft ) − y t ;
ΦT Φ(vet (k) + x

ft
x

(k)

(k)

= xt

[U t−1

+

=

2

vt
= Θt (:, end);

(k+1)
(k)
(k)
ft − 12 ∇xt f (vet (k) , x
ft ) ;
xt
= Γ µk g x
2
where Γ µk g (·) is given as in RAMSIA [19];
2
// Computing the updated weights
[19].
(k+1)
n(|xti
− zji | + )−1
wji = P
;
n
(k+1)
(|xtl
− zjl | + )−1
l=1
−1

(k+1)
(k+1)
− zj
)||1 + 
||Wj (xt
βj = J 
−1 ;
P
(k+1)
(k+1)
||Wl (xt
− zl
)||1 + 
l=0
p
ξk+1 = (1 + 1 + 4ξk2 )/2; µk+1 = max(µk , µ̄)
k = k + 1;
end
// Updating prior information.
(k+1)
Z t := {z j = xt−J+j }Jj=1 ;
B t = U t (:, 1 : d)Γ µk g1 (Σt )(1 : d, 1 : d)V t (:, 1 : d)T ;
2
// Output.
(k+1)
(k+1)
, vt
, Z t, Bt;
return xt



mt ≥ 2α log PJ

et
kδ t k2

 T
V t−1
·
0T

n

j=0

0
1



· Ve .


βj sj

J


7 X
βj sj + 1. (9)
+
5 j=0

2) If v t is slowly-changing, i.e, B t−1 and [B t−1 v t ] are low
rank. We solve the convex problem in (4) and let x̂t and
v̂ t denote its solutions. Supposing that the measurement
error of v t is bounded as kΦ(v̂ t − v t )k2 < σ, we have
that kx̂t − xt k2 ≤ 1−2σ√ρ with 0 < ρ < 1 provided
J




α
n
7 X
3
log PJ
+
βj sj + ,
ρ
5ρ j=0
2ρ
j=0 βj sj
(10)
sj
J
P
2 P
βj
w2 in both (9) and (10), wherein
where α = 2
η̂ j=0 i=1 ji
n P
−1 o
n
1
 > 0 and η̂ = min n
.
|xti −zji |+
mt ≥ 2

B t = U t (:, 1 : d)Γ µk g1 (Σt )(1 : d, 1 : d)V t (:, 1 : d)T . The
2
advantage of using incSVD is that the computational cost of
incSVD(·) is lower than conventional SVD [14], [20] since
we only compute the full SVD of the middle matrix with size
(d + 1) × (d + 1), where d  n, instead of n × (d + 1). The
computation of incSVD(·) is elaborated below.
Our goal is to compute incSVD[B t−1 v t ], i.e., [B t−1 v t ] =
n×d
U t Σt V T
, we take the SVD
t . Given matrix B t−1 ∈ R
of B t−1 to obtain B t−1 = U t−1 Σt−1 V T
t−1 . Therefore, we
can derive (U t , Σt , V t ) via (U t−1 , Σt−1 , V t−1 ) and v t . We
recast the matrix of [B t−1 v t ] by

δt
Σt−1
]·
0T
kδ t k2

VT
t−1
0T

Theorem III.1. The problem in (4) requires mt measurements to successfully separate xt ∈ Rn with the sparse
support s0 and v t ∈ Rn given compressive measurements
y t = Φ(xt + v t ), where Φ ∈ Rmt ×n , whose elements are
randomly drawn from an i.i.d. Gaussian distribution, and prior
information including the prior Z t−1 := {z j }Jj=1 , where
kxt − z j k0 = sj with z j ∈ Rn , and the prior B t−1 ∈ Rn×d .
1) If v t is not changing in time, we can recover xt successfully from (4) provided

Θt = U t Γ µk g1 (Σt )V Tt ;

[B t−1 v t ] = [U t−1



III. P ERFORMANCE G UARANTEES
A bound is presented for the minimum number of measurements required for successful separation by solving the
problem (4). This will also serve as a bound for the proposed
CORPCA method. We assume that v t is either fixed or slowlychanging incurring an measurement error that is bounded by
σ, i.e., kΦ(v̂ t − v t )k2 < σ, where v̂ t is any recovered
background. Let s0 denote the support of the source x and
sj denote the support of each difference vector x − z j ;
namely, kx − z j k0 = sj , where j ∈ {0, . . . , J}. We shall
derive the bound for recovering foreground xt given either
fixed v t or the error bound σ.

(U t , Σt , V
ht ) = 
i
(k)
ft )
incSVD B t−1 vet (k) − 12 ∇vt f (vet (k) , x
;
(k+1)

δt
e , Σt = Σ,
e and V t =
]·U
kδ t k2

0
1


,

(8)
where et = U T
v
and
δ
=
v
−
U
e
.
By
taking
t
t
t−1 t
t−1 t
SVD
of the matrix

 in between the right side of (8), we yield
Σt−1
et
eΣ
e Ve T . Eventually, we obtain U t =
= U
0T
kδ t k2

j

i=1

Proof: We firstly derive the bound in (9) of Theorem III.1
for which the low-rank component v t is not changed and the
remaining bound is a noisy case when the low-rank component
v t is slowly-changing. We drive the bounds based on Proposition VII.1 (see Appendix VII-B3) by first computing the
subdifferential ∂g(x) and then the distance, dist(·), between
the standard normal vector g and ∂g(x). The u ∈ ∂g(x) of
g(x) is derived
through the separate components of the sum
PJ
g(x) = j=0 βj gj (x), where gj (x) = kWj (x − z j )k1 . As
PJ
a result, ∂g(x) = j=0 βj ∂gj (x).
Considering the distance from the standard normal vector g
to the subdifferential ∂g(x) given by (36), we derive a relation
between this distance and all separate distances of gj (x) as
2

dist (g, τ · ∂g(x)) ≤

J
X
j=0

βj dist2(g, τ · ∂gj (x)),

(11)

4

where

PJ

j=0

βj = 1. Taking the expectation of (11) delivers

Eg [dist2 (g, τ ·∂g(x))] ≤

J
X

βj Eg [dist2 (g, τ ·∂gj (x))]. (12)

j=0

1) Distance Expectation: We now consider each component Eg [dist2(g, τ · ∂gj (x))], where gj (x) = kWj (x − z j )k1 .
We firstly consider x − z j . Without loss of generality, we
have assumed that the sparse vector x − z j has sj supports or kx − z j k0 = sj , i.e, taking the form x − z j =
(x1 − zj1 , ..., xsj − zjsj , 0, ..., 0). We have the subdifferential
u ∈ ∂gj (x) of gj (x) given by:

ui = wji sign(xi − zji ),
i = 1, ..., sj
(13)
|ui | ≤ wji ,
i = sj + 1, ..., n.
Let us recall the weights as proposed in RAMSIA [19] for
aPspecific z j with wji = ηj /(|xi − zji | + ) and the constraint
n
i=1 wji = n. Taking the source x − z j to derive

ηj
i = 1, ..., sj
|xi −zji |+ ,
(14)
wji =
ηj
i = sj + 1, ..., n.
 ,
Pn
From the constraint
w = n, we can derive: ηj =
P
−1 i=1 ji
n
1
.
n
|xi −zji |+
i=1

We can then compute the distance from the standard normal
vector g to the subdifferential ∂gj (x) based on (36) as
dist2 (g, τ · ∂gj (x)) =
+

sj 
X

gi − τ wji sign(xi − zji )

i=1
n
X



max(|gi | − τ wji , 0)

2

2

(15)
,

i=sj +1

where max(a, 0) returns the maximum value between a ∈ R
and 0. Further, after taking the expectation of (15), we obtain
2

Eg [dist (g,τ · ∂gj (x))] = sj + τ

2

sj
X

2
wji

i=1

r
+

(16)
Z ∞
n
2 X
−v 2 /2
(v − τ wji )e
dv.
π i=s +1 τ wji

ψ(τ η /)

ψ(x)/x decreases with x > 0. Thus τ ηjj/
Considering the last term in (18), we derive
2

Eg [dist (g, τ · ∂g(x))] ≤

J
X

βj sj + τ

j=0



+2 n−

2

J
X

βj

j=0
J
X
j=0

βj sj

ψ(τ η
b/)
τη
b/ .

≤
sj
X

2
wji

i=1

 ψ(τ ηb/)
τ ηb/

(19)
.

PJ
Inequality (19) holds due to
j=0 βj (n − sj ) = n −
PJ
j=0 βj sj .
PJ
We denote s̄ = j=0 βj sj and from (39), (19), we have
sj
J
n
X
X
ψ(τ ηb/) o
2
2
Ug = min s̄ + τ
. (20)
βj
wji
+ 2(n − s̄)
τ ≥0
τ ηb/
j=0
i=1

Inserting (40) in (20) gives
sj
2 2
2
J
n
X
X
2 e(−τ ηb /2 ) o
2
Ug ≤ min s̄+τ 2
βj
wji
+(n− s̄) √
.
τ ≥0
τ ηb/
2π
j=0
i=1
(21)
To give a bound as a function of a given source x and
other parameters, we can select a parameter
p τ > 0 to obtain
an useful bound in (21). Setting τ = (/b
η ) 2 log(n/s̄) gives
sj
J
n 2 X X 2
s̄(1 − s̄/n)
Ug ≤ s̄ + 2 log( ) 2
βj
. (22)
w +p
s̄ ηb j=0 i=1 ji
π log(n/s̄)

Psj
2 PJ
2
We denote α = ηb 2 j=0 βj i=1
wji
in the second term in
(22). Finally, applying the inequality (41) to the last term in
(22) gives
n
7
(23)
Ug ≤ 2α log( ) + s̄.
s̄
5
As a result, from Proposition VII.1 (in Appendix VII), we get
the bound in (9) as
n
7
mt ≥ 2α log( ) + s̄ + 1.
(24)
s̄
5
For slowly-changing v t , we assume that the measurement error
kΦ(v̂ t −v t )k2 < σ. Applying Proposition VII.1 (see Appendix
VII) for the noisy case, we get the bound in (10).

j

We use the inequality (42) for the third term in (16) to get
sj
X

n
X
ψ(τ wji )
.
τ wji
i=1
i=sj +1
(17)
2) Bound Derivation: Inserting (17) in (12) for all functions
gj (x) gives

Eg [dist2 (g, τ · ∂gj (x))] ≤ sj + τ 2

2

Eg [dist (g, τ · ∂g(x))] ≤

J
X

2
wji
+2

βj sj + τ

j=0
J
X

2

J
X
j=0

βj

sj
X
i=1

2
wji

(18)

ψ(τ ηj /)
+2
,
βj (n − sj )
τ ηj /
j=0
where wji = ηj / in (14) are used in the third term of (18).
Let us denote ηb = min{ηj }. It can be noted that the function
j

IV. N UMERICAL E XPERIMENT
We evaluate the performance of our Algorithm 1 employing the proposed method, the existing `1 minimization [21],
and the existing `1 -`1 [23], [24] minimization methods. We
also compute the established bound (10) in Theorem III.1,
which serves as an estimate of number of measurements
that CORPCA requires for successful recovery. We generate
our data as follows. We generate the low-rank component
L = U V T , where U ∈ Rn×r and V ∈ R(d+q)×r are
random matrices whose entries are drawn from the standard
normal distribution. We set n = 500, r = 5 (rank of L),
and that d = 100 is the number of vectors for training
and q = 100 is the number of testing vectors. This yields
L = [x1 ... xd+q ]. We generate S = [v 1 ... v d+q ], where at
time instance t − 1, xt−1 ∈ Rn is generated from the standard
normal distribution with support s0 . Our purpose is to consider

5
8

8
8

Foreground

30

50

50
30

Bound mt
0
10

150 250 350 450
Measurements m

30

0

150 250 350 450
Measurements m

30
10

100

90

90

70
50

50
30

Nonzeros s0

50

100

Pr(success) [%]

Nonzeros s0

70

0
10

150 250 350 450
Measurements m

100

50

Background

90

Nonzeros s0

50

50

0
10

150 250 350 450
Measurements m

Background

70

Background
100

Pr(success) [%]

10

Bound m`1

Pr(success) [%]

50

70

90

Nonzeros s0

70

Foreground

100

Bound m`1 !`1

Pr(success) [%]

Nonzeros s0

Nonzeros s0

90

Pr(success) [%]

100

90

70
50

50
30

50

0
10

Pr(success) [%]

Foreground

0

150 250 350 450
Measurements m

150 250 350 450
Measurements m

50

70
50
50

TABLE I

50

Pr(success) [%]

50

Pr(success) [%]

50

70

Nonzeros s0

70

Pr(success) [%]

Nonzeros s0

(b) `1 -`Foreground
(c) `1 Foreground
minimization
(d) Scale
1 minimization
100
100
100
Fig. 1. The90
averages of success probabilities and bounds
(a)-(c), to recover xt ∈ R500 , where the x-axis is the
90 of CORPCA with different minimizations
90
number of measurements m and the y-axis is the number of nonzeros s0 . The gray scale (d) is proportional to Pr(sussess) from pure black to white.

Nonzeros s0

(a) n-`1Foreground
minimization

a sequence of correlated sparse vectors xt . Therefore, we
S UMMARY OF RECOVERY CHARACTERISTICS
30 This could lead
generate x30
30
t satisfying kxt − xt−1 k0 = s0 /2.
Bound mt
Bound
mt GRASTA ReProCS
CORPCA
RPCA
to kxt k0 >
kx k , we set theBound mt
10s0 . To avoid a large increase of10
0 t 0
0
10
0
[1]
[7]
[10]
constraint kxt k0 150
∈ [s0250
, s0 +350
15], 450
whenever kxt k0150
> s0250
+ 15,350 450
150 250 350 450
Online
X
X
X
Measurements
xt is randomly reset
to kxt k0 m
= s0 by setting kx
k
−
s
Measurements
m
Measurements m
t 0
0
Full
data
X
X
X
X
positions that are randomly
selected
to
zero.
In
this
work,
we
Background
Background
Background
Foreground
X
X
100
test our algorithms for s0 = 10 to 90.
100
100
Compressed
90 information is initialized as follows.
90
X
90 Background X
Our prior
To illustrate
real scenarios,
70 where we do not know the sparse
70 and low-rank
70
components, we use the batch-based RPCA 50
[1] to separate the employing n-`
minimization: that, at certain 50
sparsity degrees,
50 1
50
50
training set
M 0 = [x1 + v 1 ... xd + v d50
] to obtain B 0 = we can recover
the 500-dimensional data from measurements
[v 1 ... v d 30
]. In this experiment, we use three
30 (J = 3) sparse of much lower
30 dimesions (m = 150 to 300, see white areas
components as prior information and we set Z 0 := {0, 0, 0}. in Fig. 1(a)). Furthermore, the measurement bound mt (red
10
0
10
01(a)) is consistent with the practical
0
We run CORPCA
(Sec.
the test set
M = [xd+1 + line in Fig. 10
results. It is
150
250II-B)
350on450
150 250 350 450
150 250 350 450
v d+1 ... xd+q + v
].
also
clear
that
the
`
and
`
-`
minimization
methods
(see
d+q
Measurements
m
1
1 1 m
Measurements m
Measurements
bt versus xt in terms Figs. 1(b)+1(c)) lead to a higher number of measurements,
We assess the accuracy of recovery x
of the success probability, denoted as Pr(success), versus thereby illustrating the benefit of incorporating multiple side
the number of measurements m. At time instance t, the information into the problem.
original source xt + z t is projected onto lower-dimensional
V. V IDEO F OREGROUND -BACKGROUND S EPARATION
observations y t having m measurements. For a fixed m, the
Pr(success) is the number of times, in which the source xt
We assess our CORPCA method in the application of
bt with an error kb
is recovered as x
xt − xt k2 /kxt k2 ≤ 10−2 , compressive video separation and compare it against existing
divided by the total 50 Monte Carlo simulations
and where we methods. We run all methods listed in Table I on typical test
√
have set parameters  = 0.8, λ = 1/ n. In addition, we will video content [25]. In this experiment, we use d = 100 frames
evaluate the obtained bound mt (10), m`1 -`1 (29), and m`1 (27) as training vectors for the proposed CORPCA as well as for
[23] in the presence of noisy measurements kΦ(v̂ t −v t )k2 < σ GRASTA [7] and ReProCS [10].
in the case of slowly-changing low-rank components v t . As
1) Visual Evaluation: We first consider backgroundshown in (10) of Theorem III.1, these bounds depend on ρ. foreground video separation with full access to the video data
We experimentally select ρ ∈ (0, 1) to give that our estimated (the data set M ); the visual results of the various methods
bound is consistent with the practical results, here we have are illustrated in Fig. 2. It is evident that, for both the video
0.6 0.4
set ρ to values of 0.8
sequences, CORPCA delivers superior visual results than the
3 ; 3 ; 3 ; and for mt m`1-`1 , and m`1 ,
respectively.
other methods, which suffer from less-details in the foreground
The results in Fig. 1(a) show the efficiency of CORPCA and noisy background images.
(c) CORPCA-n-`1

150 250 350 450
Measurements m

Fig. 1. Average success probabilities and bounds for the proposed CORPCA algorithm deploying the different minimizations (a)-(c), to
recover xt , v t ∈ R500 . The scale (d) is proportional to Pr(success)[%] from black to white.

(e) CORPCA-`1

J
n
o
X
1
min H(x)= kΦx − yk22 + λ βj kWj (x − z j )k1 ,
x
2
j=0

(f) ReProCS

where λ > 0, βj >0 are weights across the side information signals,
and Wj is a diagonal matrix with weights for each element in the
side information signal z j ; namely, Wj = diag(wj1 , wj2 , ..., wjn )

(g) GRASTA

10

(h) Scale

150 250 350 450
Measurements m

010

(e) CORPCA-`1

Pr(success) [%]

Nonzeros s0

Bound m!`1

150 250 350 450
Measurements m

Fig. 1. Average success probabilities and bounds for the proposed CORPCA algorithm deploying the different minimizations (a)-(c), to
recover xt , v t ∈ R500 . The scale (d) is proportional to Pr(success)[%] from black to white.

(f) ReProCS

50
30

60
40
20

010

70
50
50

50
30
10

0

150 250 350 450
Measurements m

(g) GRASTA

100
90

70

150 250 350 450
Measurements m

(h) Scale

30

Foreground

010

90

Bound m!`1

150 250 350 450
Measurements m

Fig. 1. Average success probabilities and bounds for the proposed CORPCA algorithm deploying the different minimizations (a)-(c), to
recover xt , v t ∈ R500 . The scale (d) is proportional to Pr(success)[%] from black to white.

70

50

J
n
o
X
1
min H(x)= kΦx − yk22 + λ βj kWj (x − z j )k1 ,
x
2
j=0

(3)

where λ > 0, βj >0 are weights across the side information signals,
and Wj is a diagonal matrix with weights for each element in the
side information signal z j ; namely, Wj = diag(wj1 , wj2 , ..., wjn )

J
n
o
X
1
min H(x)= kΦx − yk22 + λ βj kWj (x − z j )k1 ,
x
2
j=0

(3)

(f) ReProCS

50
30

80
60
40
20

010

0

150 250 350 450
Measurements m

(h) Scale
Fig. 4. Average success probabilities for CORPCA (for xt , v t ), ReProCS (for xt ), and GRASTA (for v t ). The scale (f) is proportional to Pr(success)[%]
Fig. 4. Average success probabilities for CORPCA (for xt , v t ), ReProCS (for xt ), and GRASTA (for v t ). The scale (f) is Fig.
proportional
to Pr(success)[%]
4. Average
success probabilities for CORPCA (for xt , v t ), ReProCS (for xt ), and GRASTA (for v t ). The scale (f) is proportional to Pr(success)[%]
from black to white.
from black to white.
from black to white.
(3)

(e) CORPCA-`1

Background

100

Nonzeros s0

70

50

Pr(success) [%]

30

Nonzeros s0

0

150 250 350 450
Measurements m

30

0

90

Pr(success) [%]

010

70
50
50

50

80

Nonzeros s0

20

90

Background

Background

100

Pr(success) [%]

40

Foreground

Nonzeros s0

30

70

Pr(success) [%]

50

100
90

90

30

150 250 350 450
Measurements m

Nonzeros s0

010

50

Bound m!`1

60

50

50

10

Background

80

70

Pr(success) [%]

150 250 350 450
Measurements m

70

Nonzeros s0

10

30

90

0

150 250 350 450
Measurements m

Pr(success) [%]

30

100

Nonzeros s0

70
50
50

50

30

Background

Pr(success) [%]

Nonzeros s0

Nonzeros s0

70

Foreground

Pr(success) [%]

100
90

90

50

50

10

Background

100

90

Pr(success) [%]

0

150 250 350 450
Measurements m

70

Pr(success) [%]

10

90

Nonzeros s0

30

(d) CORPCA-`1 -`1

Foreground

100

Pr(success) [%]

Nonzeros s0

50

50

Pr(success) [%]

(d) CORPCA-`1 -`1

Foreground

100

70

Pr(success) [%]

Nonzeros s0

(d) CORPCA-`1 -`1

Foreground

90

(c) CORPCA-n-`1

Pr(success) [%]

Nonzeros s0

Nonzeros s0

(c) CORPCA-n-`1

where λ > 0, βj >0 are weights across the side information signals,
and Wj is a diagonal matrix with weights for each element in the
side information signal z j ; namely, Wj = diag(wj1 , wj2 , ..., wjn )

(g) GRASTA

6

Original
Original

CORPCA
CORPCA
CORPCA
CORPCA

CORPCA
CORPCA

GRASTA
RPCA
GRASTA
RPCA
GRASTA
RPCA (b) Bootstrap
GRASTA
RPCA

GRASTA
RPCA
(a) Bootstrap
(b) Bootstrap
RPCA

ReProCS
ReProCS
ReProCS
ReProCS

ReProCS
ReProCS

GRASTA

m/n==0.8
0.8
m/n
m/n==0.8
0.8
m/n

m/n==0.6
0.6
m/n
m/n==0.6
0.6
m/n

m/n = 0.8
m/n = 0.8

m/n==0.4
0.4
m/n
m/n==0.4
0.4
m/n

m/n = 0.6
m/n = 0.6

m/n==0.2
0.2
m/n
m/n==0.2
0.2
m/n

m/n = 0.4
m/n = 0.4

(a) Bootstrap

m/n = 0.2
m/n = 0.2

Original
Original

CORPCA
CORPCA
CORPCA
CORPCA

RPCA
RPCA
RPCA
RPCA

GRASTA
GRASTA
GRASTA

(c) Curtain GRASTA

ReProCS
ReProCS
ReProCS
ReProCS

Fig. 2.

(c) Curtain
Background and foreground separation for the different separation methods with full data of frames Bootstrap#2210 and Curtain#2866.

Fig. 2.

Background and foreground separation for the different separation methods with full data of frames Bootstrap#2210 and Curtain#2866.

CORPCA
CORPCA

(b) Curtain

RPCA
GRASTA
ReProCS
established the theoretical
bounds on the number of required meaRPCA
GRASTA
ReProCS
surements to guarantee successful recovery. Furthermore, we have

defined as in [?].
For comparing
defined
as in [?]. CORPCA to RPCA, GRASTA, and ReProCS, Fig.
5 For
illustrates
the ROC
results
for full GRASTA,
data access,
m/n =
1,
comparing
CORPCA
to RPCA,
andi.e.,
ReProCS,
Fig.
RPCA,the
GRASTA,
and ReProCS
support
separation
5since
illustrates
ROC results
for full can
datanot
access,
i.e.,them/n
= 1,
for both
foregrounds
the compressive
measince
RPCA,
GRASTA,and
andbackgrounds
ReProCS canfrom
not support
the separation
surements.
The resultsand
of CORPCA
are from
betterthe
thancompressive
all the remaining
for
both foregrounds
backgrounds
meamethods, especially,
it is
improved
for all
Curtain
in Fig.
surements.
The results
of significantly
CORPCA are
better than
the remaining
5(b). Theespecially,
ROC results
for CORPCA,
CORPCA-n-`
1 , is depicted
methods,
it is significantly
improved
for Curtain
in Fig.
in Figs.
andresults
?? forforBootstrap
and Curtain
5(b).
The ??
ROC
CORPCA, CORPCA-n-`
depicted
1 , issequences,
respectively.
CORPCA-n-`
performances
with
1 still maintain
in
Figs. ?? and
?? for Bootstrap
andgood
Curtain
sequences,
the small number
of measurements,
e.g.,good
for performances
Bootstrap with
until
respectively.
CORPCA-n-`
1 still maintain
m/nsmall
= 0.6
[see Fig.
??] and for Curtain
until m/n =until
0.4
the
number
of measurements,
e.g., for Bootstrap
[see Fig.
Furthermore,
ReProCSuntil
fromm/n
compressive
m/n
= ??].
0.6 [see
Fig. ??] we
andsimulate
for Curtain
= 0.4
measurements
for obtainingweonly
foreground
andfrom
comprared
with
[see
Fig. ??]. Furthermore,
simulate
ReProCS
compressive
CORPCA withfor
different
measurement
rates as and
shown
in Fig. 6.with
The
measurements
obtaining
only foreground
comprared
ROC results
fordifferent
ReProCSmeasurement
are quickly degradated
for the
CORPCA
with
rates as shown
in compressive
Fig. 6. The
measurements
with aare
high
rate m/n
= 0.8.for the compressive
ROC
results foreven
ReProCS
quickly
degradated
measurements even with a high rate m/n = 0.8.
IV. C ONCLUSION
C ONCLUSION
This paper proposed aIV.
compressive
online robust PCA algorithm

established the theoretical bounds on the number of required meaFig. 2. Background and foreground separation
forresults
thethatdifferent
separation
presented numerical
showed
the Furthermore,
efficiency
of CORPCA
surements
to guarantee
successful
recovery.
we have
and the consistency
of
the theoretical
presented
numerical results
that
showedbounds.
the efficiency of CORPCA
methods with full data access Bootstrap#2213
and
Curtain#2866.
and the consistency of the theoretical bounds.

Fig. 3 presents the results of CORPCA under various rates
on the number of measurements m over the dimension n of the
data (the size of the vectorized frame). The results show that
we can recover the foreground and background even by accessing a small number of measurements; for instance, we can
obtain good-quality reconstructions with only m/n = 0.6 and
m/n = 0.4 for Bootstrap [see Fig. 3(a)] and Curtain
(CORPCA)
can process
a data vector
timePCA
instance
from
This paperthat
proposed
a compressive
online per
robust
algorithm
[see
Fig.
respectively.
Bootstrap
requires more meacompressive
measurements.
efficiently
incorporates
(CORPCA)
that
can 3(b)],
processCORPCA
a data
vector
per time
instance multifrom
ple prior information
based CORPCA
on the n-`efficiently
minimization
problem.
We
compressive
measurements.
incorporates
multisurements
than
dueWeto the more complex foreground
ple
prior information based
on theCurtain
n-` minimization problem.
information. For comparison, we illustrate the visual results
obtained with ReProCS—which, however, can only recover
the foreground using compressive measurements—in Fig. 4.
It is clear that the reconstructed foreground images have a
poorer visual quality compared to CORPCA even at a high
rate m/n = 0.81 . We consider two videos [25], Bootstrap
(60×80 pixels) and Curtain (64×80 pixels) [c.f., Fig. 2],
having a static and a dynamic background, respectively.
2) Quantitative Results: We evaluate quantitatively the separation performance via the receiver operating curve (ROC)
metric [27]. The metrics True positives and False positives are
defined as in [27].
The ROC results for CORPCA deploying different recovery
algorithms, CORPCA-n-`1 , CORPCA-`1 -`1 , and CORPCA`1 , are depicted in Fig. 5 for Bootstrap and Curtain
sequences. It is clear that CORPCA-`1 -`1 [see Figs. 5(b), 5(e)]
and CORPCA-`1 [see Figs. 5(c), 5(f)] give worse curves compred with CORPCA-n-`1 [see Figs. 5(a), 5(d)]. Specifically,
CORPCA-n-`1 gives high performances with a small number
of measurements, e.g., for Bootstrap until m/n = 0.6 [see
Fig. 5(a)] and for Curtain until m/n = 0.4 [see Fig. 5(d)].
Fig. 6 illustrates the ROC results when assuming full data
access, i.e., m/n = 1, of CORPCA, RPCA, GRASTA, and
ReProCS. The results show that CORPCA delivers higher performance than the other methods, especially for the Curtain
video sequence [c.f., Fig. 6(b)]. Furthermore, we compare
the foreground recovery performance of CORPCA against

0.8
m/n==0.8
m/n
0.8
m/n==0.8
m/n

m/n==0.6
0.6
m/n
m/n==0.6
0.6
m/n

m/n = 0.8
m/n = 0.8

m/n==0.2
0.2
m/n
m/n==0.2
0.2
m/n

m/n==0.4
0.4
m/n
m/n==0.4
0.4
m/n

m/n = 0.6
m/n = 0.6

m/n = 0.4
m/n = 0.4

m/n = 0.2
m/n = 0.2

(b) Curtain
Fig. 3. Compressive background and foreground separation of CORPCA
with different measurement rates m/n.
0.8
m/n==0.8
m/n
0.8
m/n==0.8
m/n

0.6
m/n==0.6
m/n
0.6
m/n==0.6
m/n

m/n = 0.8
0.8
m/n
m/n ==0.8

m/n==0.2
0.2
m/n
m/n==0.2
0.2
m/n

m/n==0.4
0.4
m/n
m/n==0.4
0.4
m/n

m/n = 0.6
m/n
0.6
m/n= =0.6

m/n = 0.4
m/n
= =0.4
m/n
0.4

m/n = 0.2
m/n
0.2
m/n== 0.2

(a) Bootstrap

1

1

1 The original test videos and the reconstructed separated sequences are
available online [26].

m/n = 0.8

m/n = 0.6

m/n = 0.4

m/n = 0.2

(b) Curtain
Fig. 4.
Compressive foreground separation of ReProCS with different
measurement rates m/n.

ReProCS for different compressive measurement rates: m/n =
{0.8; 0.6; 0.4; 0.2}. The ROC results in Fig. 7 show that
CORPCA achieves a relatively high performance with a small
number of measurements.
VI. C ONCLUSION
This paper proposed a compressive online robust PCA
with prior information for recursive separation. The proposed
CORPCA method can process one data frame per time instance from compressive measurements. CORPCA efficiently
incorporates multiple prior information based on the n-`1
minimization problem. To express the performance, we established the theoretical bounds on the number of required
measurements to guarantee successful recovery. The numerical
results showed the efficiency of CORPCA in terms of both the
practical results and the theoretical bounds. The results also
revealed the advantage of incorporating prior information by
employing n-`1 minimization to achieve significant improvements over that of using the existing `1 -`1 and `1 minimization
methods. We also test our method on the compressive video
separation application using video data. The results revealed
the advantage of incorporating prior information by employing
n-`1 minimization and demonstrated the superior performance

7

ROC curve of dataset -- bootstrap

ROC curve of dataset -- bootstrap

1

0.4

CORPCA-n-`1 :
CORPCA-n-`1 :
CORPCA-n-`1 :
CORPCA-n-`1 :
CORPCA-n-`1 :

0.4
0.3

0.1

0
0

0.1

0.2

0.3

CORPCA-`1 -`1 :
CORPCA-`1 -`1 :
CORPCA-`1 -`1 :
CORPCA-`1 -`1 :
CORPCA-`1 -`1 :

0.2

0

0.02

(a) Bootstrap: CORPCA-n-`1

0.04

1

0.8

0.8
CORPCA-n-`1 :
CORPCA-n-`1 :
CORPCA-n-`1 :
CORPCA-n-`1 :
CORPCA-n-`1 :

m=n = 1
m=n = 0:8
m=n = 0:6
m=n = 0:4
m=n = 0:2

0.2
0
0.04

0.06

0.1

0.08

0.1

0

0.12

0

0.002 0.004 0.006 0.008

ROC curve of dataset -- curtain

0.6

0.4
CORPCA-`1 -`1 :
CORPCA-`1 -`1 :
CORPCA-`1 -`1 :
CORPCA-`1 -`1 :
CORPCA-`1 -`1 :

m=n = 1
m=n = 0:8
m=n = 0:6
m=n = 0:4
m=n = 0:2

0.4

0

0.005

0.01

0.015

0.02

0.025

CORPCA-`1 :
CORPCA-`1 :
CORPCA-`1 :
CORPCA-`1 :
CORPCA-`1 :

0.3

(d) Curtain: CORPCA-n-`1

0.1
0

0.03

0

0.5

1

(f) Curtain: CORPCA-`1

ROC for CORPCA deploying different sparse recovery algorithms with different measurement rates for Bootstrap.

ROC curve of dataset -- curtain

ROC curve of dataset -- bootstrap

1

0.8

True positives

True positives

0.9
0.8
0.7
0.6

CORPCA
RPCA
GRASTA
ReProCS

0.5

0.6

0.4

CORPCA
RPCA
GRASTA
ReProCS

0.2

0.4
0.4

0.6

0.8

0

0.02

False positives

0.06

0.08

(b) Curtain

ROC for the different separation methods with full data.

ROC curve of dataset -- curtain

1

1

0.8

0.8

0.6
CORPCA-m=n = 0:8
CORPCA-m=n = 0:6
CORPCA-m=n = 0:4
CORPCA-m=n = 0:2
ReProCS-m=n = 0:8
ReProCS-m=n = 0:6
ReProCS-m=n = 0:4
ReProCS-m=n = 0:2

0.4

0.2

0

True positives

True positives

ROC curve of dataset -- bootstrap

CORPCA-m=n = 0:8
CORPCA-m=n = 0:6
CORPCA-m=n = 0:4
CORPCA-m=n = 0:2
ReProCS-m=n = 0:8
ReProCS-m=n = 0:6
ReProCS-m=n = 0:4
ReProCS-m=n = 0:2

0.6

0.4

0.2

0
0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

False positives

(a) Bootstrap
Fig. 7.

0.04

False positives

(a) Bootstrap
Fig. 6.

ROC for CORPCA and ReProCS with compressive measurements.

0

1.5

False positives

(e) Curtain: CORPCA-`1 -`1

1

0.02

0.04

m=n = 1
m=n = 0:8
m=n = 0:6
m=n = 0:4
m=n = 0:2

0.2

False positives

0.2

0.012 0.014

(c) Bootstrap: CORPCA-`1

0.6

False positives

0

0.01

False positives

0

0.12

m=n = 1
m=n = 0:8
m=n = 0:6
m=n = 0:4
m=n = 0:2

0.5

0.2

0.02

0.08

ROC curve of dataset -- curtain

True positives

True positives

0.06

CORPCA-`1 :
CORPCA-`1 :
CORPCA-`1 :
CORPCA-`1 :
CORPCA-`1 :

0.1

(b) Bootstrap: CORPCA-`1 -`1

ROC curve of dataset -- curtain

0

0.2

False positives

1

0.4

0.3

0

0.4

False positives

0.6

m=n = 1
m=n = 0:8
m=n = 0:6
m=n = 0:4
m=n = 0:2

True positives

0.2

m=n = 1
m=n = 0:8
m=n = 0:6
m=n = 0:4
m=n = 0:2

True positives

0.6
0.4

0.5

True positives

True positives

0.5

0.6

0.8

Fig. 5.

ROC curve of dataset -- bootstrap

0.7

0.06

0.08

False positives

(b) Curtain

0.1

0.12

2
#10 -3

8

improvement offered by CORPCA compared to the existing
methods.
VII. A PPENDIX
A. Prior Art in Compressed Sensing
The problem of recursive signal recovery employs Compressed Sensing (CS) [4], [5] to recover sparse components
from low-rank components [12], [17], which is considered as
a dynamic CS. Therefore, we review some related CS results
before stating our contributions. Let x ∈ Rn denote a highdimensional sparse vector. The source x can be reduced by
sampling via a linear projection at the encoder [4]. We denote
a random measurement matrix by Φ ∈ Rm×n (with m  n),
whose elements are sampled from an i.i.d. Gaussian distribution. Thus, we get a measurement vector y = Φx, with
y ∈ Rm . At the decoder, x can be recovered by solving the
Basis Pursuit problem [4], [5]:
min kxk1 subject to y = Φx,
(25)
x
Pn
where kxkp := ( i=1 |xi |p )1/p is the `p -norm of x wherein
xi is an element of x. Problem (25) becomes an instance of
finding a general solution:
min{H(x) = f (x) + g(x)},
x

(26)

where f := Rn → R is a smooth convex function and g :=
Rn → R is a continuous convex function, which is possibly
non-smooth. Problem (25) emerges from Problem (26) when
setting g(x) = λkxk1 and f (x) = 12 kΦx − yk22 , with
Lipschitz constant L∇f [21].
We consider how many measurements are required for
successful recovery. The classical `1 minimization problem in
CS [4], [5], [28] requires m`1 measurements [23], [24], [29]
for successful reconstruction, bounded as
n
7
m`1 ≥ 2s0 log
(27)
+ s0 + 1,
s0
5
where s0 := kxk0 = |{i : xi 6= 0}| denotes the number of
nonzero elements in x as the support of x, with |.| denoting
the cardinality of a set and k · k0 being the `0 -pseudo-norm.
Furthermore, the `1 -`1 minimization approach [23], [24],
[30] reconstructs x given a signal z ∈ Rn as side information
by solving the following problem:
o
n1
min
kΦx − yk22 + λ(kxk1 + kx − zk1 ) .
(28)
x
2
The bound on the number of measurements required by
Problem (28) to successfully reconstruct x depends on the
quality of the side information signal z as [23], [24], [30]

 7
n
ξ
m`1 -`1 ≥ 2h log
+
s0 +
+ 1,
(29)
s0 + ξ/2
5
2
where
ξ : = |{i : zi 6= xi = 0}| − |{i : zi = xi 6= 0}|
h̄ : = |{i : xi > 0, xi > zi } ∪ {i : xi < 0, xi < zi }|,
wherein xi , zi are corresponding elements of x, z. It has been
shown that Problem (28) improves over Problem (25) provided
that the side information has good enough quality [23], [24].

B. Background on Measurement Condition
We restate some key definitions and conditions in convex
optimization [29], [31], which are used in the derivation of
the measurement bounds.
A convex cone C ⊂ Rn is a convex set that satisfies C =
τ C, ∀τ ≥ 0 [31]. For the cone C ⊂ Rn , a polar cone C ◦ is
the set of outward normals of C, defined by
C ◦ := {u ∈ Rn : uT x ≤ 0, ∀x ∈ C}.

(31)

A descent cone [31, Definition 2.7] D(g, x), alias tangent
cone [29], of a convex function g := Rn → R at a point
x ∈ Rn —at which g is not increasing—is defined as
[
D(g, x) :=
{y ∈ Rn : g(x + τ y) ≤ g(x)},
(32)
τ ≥0

S
where
denotes the union operator.
Recently, a new summary parameter called the statistical
dimension δ(C) of cone C [31] is introduced to estimate the
convex cone [31, Theorem 4.3]. The statistical dimension can
be expressed in terms of the polar cone C ◦ as [31, Proposition
3.1]

δ(C) := Eg dist2 (g, C ◦ )].
(33)
1) Gaussian Width: The Gaussian width [29] is a summary
parameter for convex cones; it is used to measure the aperture
of a convex cone. For a convex cone C ⊂ Rn , considering
a subset C ∩ Sn−1 where Sn−1 ⊂ Rn is a unit sphere, the
Gaussian width [29, Definition 3.1] is defined as
ω(C) := Eg [

sup

g T u].

(34)

u∈C∩Sn−1

where g ∼ N(0, In ) is a vector of n independent, zero-mean,
and unit-variance Gaussian random variables and Eg [·] denotes
the expectation with respect to g. The Gaussian width [29,
Proposition 3.6] can further be bounded as

ω(C) ≤ Eg dist(g, C ◦ )],
(35)
where dist(g, C ◦ ) denotes the Euclidean distance of g with
respect to the set C ◦ , which is in turn defined as
dist(g, C ◦ ) := min{kg − uk2 : u ∈ C ◦ }.
u

(36)

2) Measurement Condition: An optimality condition [29,
Proposition 2.1], [31, Fact 2.8] for linear inverse problems
states that x0 is the unique solution of (26) if and only if
D(g, x0 ) ∩ null(Φ) = {0},

(37)

where null(Φ) := {x ∈ Rn : Φx = 0} is the null
space of Φ. We consider the number of measurements m
required to successfully reconstruct a given signal x0 ∈ Rn .
Corollary 3.3 in [29] states that, given a measurement vector
y = Φx0 , x0 is the unique
solution of (26) with probability
√
at least 1 − exp(− 12 ( m − ω(D(g, x0 )))2 ) provided that
m ≥ ω 2 (D(g, x0 )) + 1.

9

3) Bound on the Measurement Condition: Let us consider
that the subdifferential ∂g [32] of a convex function g at
a point x ∈ Rn is given by ∂g := {u ∈ Rn : g(y) ≥
g(x) + uT (y − x) for all y ∈ Rn }. From (33), (35), and [31,
Proposition 4.1], we obtain an upper bound on δ(D(g, x)) as


ω 2 (D(g, x0 )) ≤ δ(D(g, x)) ≤ min Eg dist2 (g, τ · ∂g(x)) .
τ ≥0

(38)
We conclude the following proposition for determine the
measurement bound.
Proposition VII.1. [29, Corrollary 3.3, Proposition 3.6] We
have the successful recovery x ∈ Rn in (26) that we have
observed measurements y = Φx, where Φ ∈ Rm×n , provided
the condition m ≥ Ug + 1. For the noisy measurements ky −
Φxk2 < σ, we have that kx − x̂k2 < 1−2σ√ρ provided the
U +3/2

condition m ≥ g ρ , where x̂ is any solution in (26) and
0 < ρ < 1. The quantity Ug is calculated given a convex norm
function g := Rn → R
h
i
Ug = min Eg dist2 (g, τ · ∂g(x)) ,
(39)
τ ≥0

where ∂g(x) is the subdifferential [32] of g(x) at a point x.
C. Some supported results
Recall that the probability density of the normal distribution
N(0, 1) with zero-mean and unit variance ψ(x) is given by
√
2
ψ(x) := (1/ 2π)e−x /2 .
(40)
We also consider the following inequality [24]:
2
(1 − x−1 )
1
p
≤ ,
≤√
5
2π
π log(x)

(41)

for all x > 1. Moreover, adhering to the formulation in [24],
we use the following inequality with x > 0 in our derivations:
Z ∞
2
1
ψ(x)
√
(v − x)2 e−v /2 dv ≤
.
(42)
x
2π x
R EFERENCES
[1] E. J. Candès, X. Li, Y. Ma, and J. Wright, “Robust principal component
analysis?” J. ACM, vol. 58, no. 3, pp. 11:1–11:37, Jun. 2011.
[2] J. Wright, A. Ganesh, S. Rao, Y. Peng, and Y. Ma, “Robust principal
component analysis: Exact recovery of corrupted low-rank matrices via
convex optimization,” in Advances in Neural Information Processing
Systems 22, 2009.
[3] Z. Lin, M. Chen, and Y. Ma, “The augmented lagrange multiplier method
for exact recovery of corrupted low-rank matrices,” University of Illinois
at Urbana-Champaign, USA, Tech. Rep., 2009.
[4] E. Candès and T. Tao, “Near-optimal signal recovery from random
projections: Universal encoding strategies?” IEEE Trans. Inf. Theory,
vol. 52, no. 12, pp. 5406–5425, Apr. 2006.
[5] D. Donoho, “For most large underdetermined systems of linear equations
the minimal `1 -norm solution is also the sparsest solution,” Communications on Pure and Applied Math, vol. 59, no. 6, pp. 797–829, 2006.
[6] L. Balzano, R. Nowak, and B. Recht, “Online identification and tracking
of subspaces from highly incomplete information,” in Proceedings of the
Allerton Conference on Communication, Control and Computing, Sep.
2010.
[7] J. He, L. Balzano, and A. Szlam, “Incremental gradient on the grassmannian for online foreground and background separation in subsampled
video,” in 2012 IEEE Conference on Computer Vision and Pattern
Recognition, June 2012.

[8] J. Feng, H. Xu, and S. Yan, “Online robust pca via stochastic optimization,” in Advances in Neural Information Processing Systems 26, 2013.
[9] H. Mansour and X. Jiang, “A robust online subspace estimation and
tracking algorithm,” in 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), April 2015.
[10] H. Guo, C. Qiu, and N. Vaswani, “An online algorithm for separating
sparse and low-dimensional signal sequences from their sum,” IEEE
Trans. Signal Process., vol. 62, no. 16, pp. 4284–4297, 2014.
[11] C. Qiu, N. Vaswani, B. Lois, and L. Hogben, “Recursive robust PCA
or recursive sparse recovery in large but structured noise,” IEEE Trans.
Inf. Theory, vol. 60, no. 8, pp. 5007–5039, 2014.
[12] J. F. Mota, N. Deligiannis, A. C. Sankaranarayanan, V. Cevher, and M. R.
Rodrigues, “Adaptive-rate reconstruction of time-varying signals with
application in compressive foreground extraction,” IEEE Trans. Signal
Process., vol. 64, no. 14, pp. 3651–3666, 2016.
[13] G. Warnell, S. Bhattacharya, R. Chellappa, and T. Basar, “Adaptiverate compressive sensing using side information,” IEEE Trans. Image
Process., vol. 24, no. 11, pp. 3846–3857, 2015.
[14] P. Rodriguez and B. Wohlberg, “Incremental principal component pursuit for video background modeling,” Journal of Mathematical Imaging
and Vision, vol. 55, no. 1, pp. 1–18, 2016.
[15] K. M. John Wright, Arvind Ganesh and Y. Ma, “Compressive principal
component pursuit,” Information and Inference, vol. 2, no. 1, pp. 32–68,
2013.
[16] C. Qiu and N. Vaswani, “Support-predicted modified-cs for recursive
robust principal components’ pursuit,” in IEEE Int. Symposium on
Information Theory, St. Petersburg, Russia, Jul. 2011.
[17] N. Vaswani and J. Zhan, “Recursive recovery of sparse signal sequences
from compressive measurements: A review,” IEEE Trans. Signal Process., vol. 64, no. 13, pp. 3523–3549, 2016.
[18] N. Vaswani and W. Lu, “Modified-cs: Modifying compressive sensing
for problems with partially known support,” IEEE Trans. Signal Process., vol. 58, no. 9, pp. 4595–4607, Sep. 2010.
[19] H. V. Luong, J. Seiler, A. Kaup, and S. Forchhammer, “Sparse signal
reconstruction with multiple side information using adaptive weights
for multiview sources,” in IEEE Int. Conf. on Image Process., Phoenix,
Arizona, Sep. 2016.
[20] M. Brand, “Incremental singular value decomposition of uncertain data
with missing values,” in European Conference on Computer Vision,
2002.
[21] A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM Journal on Imaging Sciences,
vol. 2(1), pp. 183–202, 2009.
[22] J.-F. Cai, E. J. Candès, and Z. Shen, “A singular value thresholding
algorithm for matrix completion,” SIAM J. on Optimization, vol. 20,
no. 4, pp. 1956–1982, Mar. 2010.
[23] J. F. Mota, N. Deligiannis, and M. R. Rodrigues, “Compressed sensing with side information: Geometrical interpretation and performance
bounds,” in IEEE Global Conf. on Signal and Information Processing,
Austin, Texas, USA, Dec. 2014.
[24] ——, “Compressed sensing with prior information: Optimal strategies,
geometry, and bounds,” ArXiv e-prints, Aug. 2014.
[25] L. Li, W. Huang, I. Y.-H. Gu, and Q. Tian, “Statistical modeling of
complex backgrounds for foreground object detection,” IEEE Trans.
Image Process., vol. 13, no. 11, pp. 1459–1472, 2004.
[26] The matlab code of the CORPCA algorithm, the test
sequences, and the corresponding outcomes. [Online]. Available:
https://github.com/huynhlvd/corpca
[27] M. Dikmen, S. F. Tsai, and T. S. Huang, “Base selection in estimating
sparse foreground in video,” in 16th IEEE International Conference on
Image Processing, Nov 2009.
[28] D. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, vol. 52,
no. 4, pp. 1289–1306, Apr. 2006.
[29] V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky, “The convex geometry of linear inverse problems,” Foundations of Computational
Mathematics, vol. 12, no. 6, pp. 805–849, 2012.
[30] J. F. Mota, N. Deligiannis, A. Sankaranarayanan, V. Cevher, and M. R.
Rodrigues, “Dynamic sparse state estimation using `1 -`1 minimization:
Adaptive-rate measurement bounds, algorithms and applications,” in
IEEE Int. Conf. on Acoustics, Speech and Signal Processing, Brisbane,
Australia, Apr. 2015.
[31] D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp, “Living on
the edge: phase transitions in convex programs with random data,”
Information and Inference, vol. 3, no. 3, pp. 224–294, 2014.
[32] J.-B. Hiriart-Urruty and C. Lemaréchal, Fundamentals of Convex Analysis. Springer, 2004.

