# Restricted Isometry Property of Principal Component Pursuit with Reduced Linear Measurements

Authors: Qingshan You; Qun Wan; Haiwen Xu
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The principal component prsuit with reduced linear measurements (PCP_RLM) has gained great attention in applications, such as machine learning, video, and aligning multiple images. The recent research shows that strongly convex optimization for compressive principal component pursuit can guarantee the exact low-rank matrix recovery and sparse matrix recovery as well. In this paper, we prove that the operator of PCP_RLM satisfies restricted isometry property (RIP) with high probability. In addition, we derive the bound of parameters depending only on observed quantities based on RIP property, which will guide us how to choose suitable parameters in strongly convex programming.


---

## Body

## 1. Introduction

Matrix completion is a signal processing technique, which recovers an unknown low-rank or approximately low-rank matrix from a sampling of its entries. Recently, this technique has been applied in many fields, such as medical [1], imaging [2], seismology [3], and computer vision [4–6]. The dimension of data produced in practice is always vastly high, therefore, there exists a pressing challenge to develop efficient and effective tools to process, analyze, and extract useful information from a small set of linear measurements of the high-dimensional data. Many scholars had studied in detail in the recent papers [7–13]. Candès et al. address the problem of recovery of the unknown low-rank matrix and sparse matrix from the sampling of its complete entries [7–9] for large scale. As the extensions of previous works, Ganesh et al. address the problem of decomposing a superposition of a low-rank matrix and a sparse matrix when a relatively few linear measurements are available [10, 11].These fundamental results have a great impact in engineering and applied mathematics. However, these results are limited into convex optimization; that is, nuclear norm based convex optimization leads to the exact low-rank matrix recovery under suitable conditions. It is well known that strongly convex optimization has many intrinsic advantages, such as the uniqueness of optimal solution. Especially, the strongly convex optimization was widely used in designing efficient and effective algorithm in the literature of compressive sensing and low-rank matrix recovery. Zhang et al. extend them; they proved that strongly convex optimizations can guarantee the exact low-rank matrix recovery as well in the paper [12]. The right bound of τ of strongly convex programming for robust principal component analysis was provided in paper [14].Pertaining to the strongly convex optimization for compressive principal component pursuit, we had studied it in detail in our former work in [15], in which we prove that under suitable conditions, the corresponding strongly convex optimization also recovers the low-rank matrix and sparse matrix exactly. However, the bound of parameter strongly depends on the Frobenius norm of the data, which is not known in practice, because the data we can use is 𝒫QM only. In this paper, we will give an easy band of τ depending on 𝒫QM only.


### 1.1. Contents and Notations

For convenience, we will give here a brief summary of the notations that will be used throughout the paper. We denoted the operator norm of matrix by∥X∥, the Frobenius norm by ∥X∥F, the nuclear norm by ∥X∥* and the l∞ norm by ∥X∥∞:=maxij|xij|. We will bound the Euclidean inner product between two matrices which is defined by the formula 〈X,Y〉=trace(X*Y). The Cauchy-Schwarz inequality gives 〈X,Y〉≤∥X∥F∥Y∥F, especially ∥X∥*≤r∥X∥F and ∑ij‍|xij|≤|X|0∥X∥F. We will also bound linear transformations which act on the space of matrices, and we denote these operators by 𝒫TX. The norm of the operator is denoted by ∥𝒫∥; that is, ∥𝒫∥=sup{∥X∥F=1}∥𝒫X∥F. We denote by Ω the support of S0. By a slight abuse of notation, we also represent by Ω the subspace of matrices whose support is contained in the support of S0. Supp(S0)~Ber(ρ) means each entry of the matrix belongs to the support of the sparse matrix S0 independently with probability ρ.


### 1.2. Basic Problem and Main Result

In this paper, we only address the strongly convex programming of principal component pursuit with reduced linear measurements, which is considered in paper [10]. This problem has the following formula:
(1)minimize∥L∥*+λ∥S∥1+12τ∥L∥F2+12τ∥S∥F2subjectto𝒫QM=𝒫Q(L+S),
where τ>0 is some positive penalty parameter and PQ is the orthogonal projection onto the linear subspace Q, and Q is distributed according to the Haar measure on the Grassmannian 𝔾(Rm×n;q). Suppose that G1,G2,…,Gp are standard orthogonal basis of Q⊥; that is, G1,G2,…,Gp are identical in distribution to G, where G=H/∥H∥F and H=M/mn, whose entries are i.i.d, according to the standard normal distribution. More detail was interpreted in the paper [10].Whenτ=∞ in the problem (1), we have existence and uniqueness theorems as follows.Theorem 1 (see [10]).
Fix anyCp>0, and let Q⊥ be a p-dimensional random subspace of ℝm×n; L0 obeys incoherence condition with parameter μ, and supp(S0)~Ber(ρ). Then, with high probability, the solution of problem (1) with λ=1/n is exact; that is, L^=L0 and S^=S0, provided that
(2)Rank(L0)<Crnμ-1(logm)-2,p<Cpn,ρ<ρ0,
where, Cr, Cp and ρ0∈(0,1) are positive numerical constants.Remark 2.
The value ofρ0 is a fixed positive numerical constant and should obey some suitable conditions; one of those is less than 1/5. the detail derivation has been well-studied (see, e.g., [8, 10] and the many references therein). With high probability means with probability at least 1-m-c, with c>0 numerical constant.
Whenτ≠∞ in the problem (1), we have existence and uniqueness theorems as follow.Lemma 3 (see [14, 15]).
Assuming(3)τ≥815∥M∥F3λ
under the other assumptions of Theorem 1, (L0,S0) is the unique solution to the strongly convex programming (1) with high probability.Pertaining to the projection operator𝒫Q, we obtain the following restricted isometry property of operator 𝒫Q restricted in a superposition of low-rank matrices and sparse matrices.Theorem 4.
Suppose thatL is low-rank matrix with rank r, S is sparse matrix with Supp(S0)~Ber(ρ), ρ≤δ2/(64×25plog(mnp)), and r≤(mnδ2/(12×25p))-(5/3)log(n), and assume that the conditions of Theorem 1 hold. Then, with high probability, one has
(4)(1-δ)∥M∥F≤∥𝒫QM∥F≤(1+δ)∥M∥F.According to Lemma3 and Theorem 4, we can easy obtain the following theorem.Theorem 5.
Supposing thatL is low-rank matrix with rank r, S is sparse matrix with Supp(S)~Ber(ρ). If
(5)τ≥815∥𝒫QM∥F3(1-δ)λ
under the other assumptions of Theorem 4, (L0,S0) is the unique solution to the strongly convex programming (1) with high probability.It is obvious that the band ofτ depends on 𝒫QM only, which is obtained very easily in practice.


### 1.3. Contributions and Organization

In this paper, we first prove that although the operator𝒫Q does not satisfy the restricted isometry property (RIP) in entire space, it obeys restricted isometry property (RIP) with high probability if the rank of low-rank matrix is not large and the sparse matrix is enough sparse. Second, we will use the restricted isometry property to improve the band of parameter which just depends on 𝒫QM.The main center of the paper provides the proof of Theorem4. The rest of paper is organized as follows. In Section 2, we will provide some important lemmas which are important composition of our main result and then will give the proof of Theorem 4. Conclusion and further works are discussed in Section 3.


## 1.1. Contents and Notations

For convenience, we will give here a brief summary of the notations that will be used throughout the paper. We denoted the operator norm of matrix by∥X∥, the Frobenius norm by ∥X∥F, the nuclear norm by ∥X∥* and the l∞ norm by ∥X∥∞:=maxij|xij|. We will bound the Euclidean inner product between two matrices which is defined by the formula 〈X,Y〉=trace(X*Y). The Cauchy-Schwarz inequality gives 〈X,Y〉≤∥X∥F∥Y∥F, especially ∥X∥*≤r∥X∥F and ∑ij‍|xij|≤|X|0∥X∥F. We will also bound linear transformations which act on the space of matrices, and we denote these operators by 𝒫TX. The norm of the operator is denoted by ∥𝒫∥; that is, ∥𝒫∥=sup{∥X∥F=1}∥𝒫X∥F. We denote by Ω the support of S0. By a slight abuse of notation, we also represent by Ω the subspace of matrices whose support is contained in the support of S0. Supp(S0)~Ber(ρ) means each entry of the matrix belongs to the support of the sparse matrix S0 independently with probability ρ.


## 1.2. Basic Problem and Main Result

In this paper, we only address the strongly convex programming of principal component pursuit with reduced linear measurements, which is considered in paper [10]. This problem has the following formula:
(1)minimize∥L∥*+λ∥S∥1+12τ∥L∥F2+12τ∥S∥F2subjectto𝒫QM=𝒫Q(L+S),
where τ>0 is some positive penalty parameter and PQ is the orthogonal projection onto the linear subspace Q, and Q is distributed according to the Haar measure on the Grassmannian 𝔾(Rm×n;q). Suppose that G1,G2,…,Gp are standard orthogonal basis of Q⊥; that is, G1,G2,…,Gp are identical in distribution to G, where G=H/∥H∥F and H=M/mn, whose entries are i.i.d, according to the standard normal distribution. More detail was interpreted in the paper [10].Whenτ=∞ in the problem (1), we have existence and uniqueness theorems as follows.Theorem 1 (see [10]).
Fix anyCp>0, and let Q⊥ be a p-dimensional random subspace of ℝm×n; L0 obeys incoherence condition with parameter μ, and supp(S0)~Ber(ρ). Then, with high probability, the solution of problem (1) with λ=1/n is exact; that is, L^=L0 and S^=S0, provided that
(2)Rank(L0)<Crnμ-1(logm)-2,p<Cpn,ρ<ρ0,
where, Cr, Cp and ρ0∈(0,1) are positive numerical constants.Remark 2.
The value ofρ0 is a fixed positive numerical constant and should obey some suitable conditions; one of those is less than 1/5. the detail derivation has been well-studied (see, e.g., [8, 10] and the many references therein). With high probability means with probability at least 1-m-c, with c>0 numerical constant.
Whenτ≠∞ in the problem (1), we have existence and uniqueness theorems as follow.Lemma 3 (see [14, 15]).
Assuming(3)τ≥815∥M∥F3λ
under the other assumptions of Theorem 1, (L0,S0) is the unique solution to the strongly convex programming (1) with high probability.Pertaining to the projection operator𝒫Q, we obtain the following restricted isometry property of operator 𝒫Q restricted in a superposition of low-rank matrices and sparse matrices.Theorem 4.
Suppose thatL is low-rank matrix with rank r, S is sparse matrix with Supp(S0)~Ber(ρ), ρ≤δ2/(64×25plog(mnp)), and r≤(mnδ2/(12×25p))-(5/3)log(n), and assume that the conditions of Theorem 1 hold. Then, with high probability, one has
(4)(1-δ)∥M∥F≤∥𝒫QM∥F≤(1+δ)∥M∥F.According to Lemma3 and Theorem 4, we can easy obtain the following theorem.Theorem 5.
Supposing thatL is low-rank matrix with rank r, S is sparse matrix with Supp(S)~Ber(ρ). If
(5)τ≥815∥𝒫QM∥F3(1-δ)λ
under the other assumptions of Theorem 4, (L0,S0) is the unique solution to the strongly convex programming (1) with high probability.It is obvious that the band ofτ depends on 𝒫QM only, which is obtained very easily in practice.


## 1.3. Contributions and Organization

In this paper, we first prove that although the operator𝒫Q does not satisfy the restricted isometry property (RIP) in entire space, it obeys restricted isometry property (RIP) with high probability if the rank of low-rank matrix is not large and the sparse matrix is enough sparse. Second, we will use the restricted isometry property to improve the band of parameter which just depends on 𝒫QM.The main center of the paper provides the proof of Theorem4. The rest of paper is organized as follows. In Section 2, we will provide some important lemmas which are important composition of our main result and then will give the proof of Theorem 4. Conclusion and further works are discussed in Section 3.


## 2. The Proof of Theorem4

In this section, we will provide the proof of Theorem4. We first bound the behaviors of the operator 𝒫Q⊥ implying on the space of low-rank matrices and the space of sparse matrices, respectively. Then, the relation of ∥M∥F and ∥L∥F+∥S∥F, we can obtain Theorem 4.


### 2.1. Bounding the Behavior of∥𝒫Q⊥(S)∥F

We will provide some important lemmas, which are used in the main theorem.Lemma 6 (see [10, Lemma 6]).
LetQ⊥ be a linear subspace distributed according to the random subspace model described earlier. Then, for any (i,j)∈[m]×[n], with high probability
(6)∥𝒫Q⊥eiejT∥F≤4plog(mnp)mn.Bernstein’s Inequality [16, 17]. Assume that X1,X2,…,Xn are independent random variables with 𝔼[Xi]=0, for all i. Furthermore, suppose that |Xi|≤M. Then,
(7)ℙ{|∑i‍Xi|>t}≤2exp(-t22∑iVar(Xi)+2Mt/3).Lemma 7.
Ifρ≥logn/mn, then with high probability
(8)∥S∥0≤2ρmn.Proof.
Letωij be the indicator variables with ωij=1 if (ij)∈Ω and ωij=0 for otherwise. For S∈Ω, we have
(9)∥S∥0≤∑ij‍ωij.
Let Yij:=ωij-ρ and Z:=∑ij‍Yij. For 𝔼[Yij]=𝔼[ωij]-ρ=0 and |Yij|≤1, it is obvious that Yij satisfies Bernstein’s inequality. Note that
(10)∑ij‍Var(Yij)=ρ(1-ρ)mn≤ρmn.
According to Bernstein’s inequality, letting t=ρmn, we have
(11)ℙ{|∑ij‍ωij-ρmn|>ρmn}≤2exp(-3ρmn8).
Combining with ρ≥logn/mn, we have
(12)ℙ{|∑ij‍ωij-ρmn|>ρmn}≤n-3/8.
In other words,∥S∥0≤2ρmn with high probability. Note that limn→∞logn/mn=0. That means ρ can obtain very small value when n is very large.Theorem  8(a).Suppose thatSis sparse matrix withSupp(S)~Ber(ρ)andQ⊥is ap-dimensional random subspace ofℝm×n. Ifρ≤δ2/64plog(mnp), with high probability, one has(13)∥𝒫Q⊥S∥F≤δ∥S∥F.Proof.
According to triangle inequality, we have(14)∥𝒫Q⊥S∥F=∥𝒫Q⊥(∑ij‍SijeiejT)∥F≤∑ij‍|Sij|∥𝒫Q⊥eiejT∥F≤4plog(mnp)mn∑ij‍|Sij|≤2ρmn∥S∥F4plog(mnp)mn≤64pρlog(mnp)∥S∥F.
In the third inequality, we have used Lemma 6. In the foarth inequality, we have used Cauchy-Schwarz inequality and Lemma 7. Combining with ρ≤δ2/64plog(mnp), we can obtain
(15)∥𝒫Q⊥S∥F≤δ∥S∥F.Theorem  8(b).Suppose thatSis sparse matrix withSupp(S)~Ber(ρ), andQ⊥is ap-dimensional random subspace ofℝm×n. Ifρ≤δ2/64plog(mnp), with high probability, one has(16)(1-δ)∥S∥F≤∥𝒫QS∥F≤(1+δ)∥S∥F.Proof.
For∥𝒫Q∥≤1, we have ∥𝒫QS∥F≤∥S∥F≤(1+δ)∥S∥F. On the other hand, we have
(17)∥𝒫QS∥F=∥S-𝒫Q⊥S∥F≥∥S∥F-∥𝒫Q⊥S∥F≥(1-δ)∥S∥F.


### 2.2. Bounding the Behavior of∥𝒫Q⊥(L)∥F

Lemma 9 (see [7, 18]).
Suppose thatYd is distributed as a chi-squared random variable with d degrees of freedom. Then, for each t>0(18)ℙ{Yd-d≥t2d+t2}≤e-t2/2,(19)ℙ{Yd≤d(1-ϵ)}≤e-ϵ2d/4.Lemma 10.
With high probability, one has(20)∥H∥F≥12.Proof.
According to the definition ofH, we have
(21)∥H∥F2=∥M∥F2mn,
where (M)ij~𝒩(0.1). It is necessary to bound ∥M∥F2. It is easy to note that ∥M∥F2 is distributed as a chi-squared random variable with mn degrees of freedom. Letting ϵ=3/4, we have
(22)ℙ{Yd≤mn(1-ϵ)}≤e-ϵ2mn/4,
where we have used (19). Equation (22) tells us: ∥M∥F2≥mn/4 with high probability. Therefore, Lemma 9 is established.Lemma 11 (see [8, 9]).
Assume thatΩ~Ber(ρ). If 1-ρ≥Cϵ-2(μrlogn/n), then with high probability
(23)∥𝒫Ω𝒫T∥2≤ρ+ϵ.According to Lemma11, if ϵ and ρ are small enough, we have the below formula with high probability
(24)∥𝒫Ω𝒫T∥≤12.Lemma 12.
Under the assumption of Theorem1, with high probability, one has
(25)∥L∥F+∥S∥F≤5∥M∥F.Proof.
Note thatL∈T, and we have
(26)∥𝒫ΩL∥F2=∥𝒫Ω𝒫TL∥F2≤14∥L∥F2=14(∥𝒫ΩL∥F2+∥𝒫Ω⊥M∥F2).
In the first inequality, we have used Lemma 11. In the second equality, we have used 𝒫Ω⊥L=𝒫Ω⊥M, because S∈Ω. It is obvious that
(27)∥𝒫ΩL∥F≤33∥𝒫Ω⊥M∥F.
Therefore,
(28)∥L∥F≤∥𝒫ΩL∥F+∥𝒫Ω⊥L∥F≤33∥𝒫Ω⊥M∥F+∥𝒫Ω⊥M∥F≤53∥M∥F.
And thus, we can obtain
(29)∥L∥F+∥S∥F=∥L∥F+∥M-L∥F≤2∥L∥F+∥M∥F≤5∥M∥F.
Lemma 12 is established.Next, we will bound the behavior of∥𝒫Q⊥(L)∥F, based on Lemma 9 to Lemma 12.Theorem  13(a).Suppose thatLber-rank matrix andQ⊥is ap-dimensional random subspace ofℝn×n. Ifr≤(mnδ2/12p)-(5/3)log(n), with high probability, one  has(30)∥𝒫Q⊥L∥F≤δ∥L∥F.As pointed out by one reviewer, Lemma 15 in [10] is similar to Theorem  13(a). Lemma 15 in [10] tells us (30) is established if r≤nδ2/pυ; however it is obvious that r is strongly based on υ which is defined as if there exists an orthonormal basis {Gi} for L satisfying maxi∥Gi∥2≤υ/n, which is very difficult to compute. The condition of r in Theorem  13(a) is just based on m,n,p, and δ, which is easy to determine.Proof.
According to the definition ofQ⊥, we have
(31)∥𝒫Q⊥L∥F=∑k=1p‍|〈Gk,L〉|2≤pmaxk|〈Gk,L〉|,
where G1,G2,…,Gk are independent and identically distributed to G mentioned before. According to (31), it is necessary to bound |〈G,L〉|. Suppose that UΣVT is singular value decomposition of matrix L; that is, L=UΣVT=∑l=1r‍σlulvlT. Therefore, according to triangle inequality, we have
(32)|〈G,L〉|≤∑l=1r‍σl|〈G,ulvlT〉|=∑l=1r‍σl|ulTGvl|≤∑l=1r‍σl2∑l=1r‍(ulTGvl)2=∥L∥F∥H∥Fmn∑l=1r‍(ulTMvl)2≤2∥L∥Fmn∑l=1r‍(ulTMvl)2,
where ul,vl are the lth rows of U,V, respectively. In the second inequality, we have used Cauchy-Schwarz inequality. In the last inequality, we have used Lemma 10. Let yl:=ulTMvl=∑ij‍ulimijvlj; note that
(33)𝔼{yl}=∑ij‍ulivlj𝔼{mij}=0,Var{yl}=∑ij‍Var{ulivljmij}=∑ij‍uli2vlj2Var{mij}=1,
where we have used the fact ∑i‍uli2=1 and ∑j‍vlj2=1. In other word yl~𝒩(0,1). Let z:=∑l=1r‍(ulTMvl)2=∑l=1r‍yl2. It is obvious that z is distributed as a chi-squared random variable with r degrees of freedom.
According to Lemma9, letting t=2logn, we can obtain
(34)ℙ(Yd≥d+2logn2d+4logn)≤n-2.
It implies that with high probability
(35)Yd≤d+2logn2d+4logn.
That is, with high probability
(36)z≤r+2logn2r+4logn.
Combining with (31), (32), and (36), with high probability, we can obtain
(37)∥𝒫Q⊥L∥F≤2p∥L∥Fmnr+2logn2r+4logn≤2p∥L∥Fmn3r+5logn,
where we have used the fact: if a,b≥0,2ab≤a+b. Let
(38)2pmn3r+5logn≤δ.
That is,
(39)r≤mnδ212p-53log(n).
Theorem  13(a) is established.Theorem  13(b).Suppose thatLisμ-incoherent matrix andQ⊥is ap-dimensional random subspace ofℝn×n. Ifr≤(mnδ2/12p)-(5/3)log(n), with high probability, one has(40)(1-δ)∥L∥F≤∥𝒫QL∥F≤(1+δ)∥L∥F.Proof.
The main idea of the proof follows the arguments of Theorem  8(b).Proof of Theorem4.
According to Theorems  8 and 13 and the assumption of Lemma3, we have
(41)∥𝒫Q⊥L∥F≤δ∥L∥F,∥𝒫Q⊥S∥F≤δ∥S∥F.
Therefore,
(42)∥𝒫Q⊥(L+S)∥F≤∥𝒫Q⊥L∥F+∥𝒫Q⊥S∥F≤δ(∥L∥F+∥S∥F)≤5δ∥M∥F.
Then,
(43)∥𝒫QM∥F=∥M-𝒫Q⊥M∥F≥∥M∥F-∥𝒫Q⊥M∥F≥(1-5δ)∥M∥F.
Theorem 4 is established.


## 2.1. Bounding the Behavior of∥𝒫Q⊥(S)∥F

We will provide some important lemmas, which are used in the main theorem.Lemma 6 (see [10, Lemma 6]).
LetQ⊥ be a linear subspace distributed according to the random subspace model described earlier. Then, for any (i,j)∈[m]×[n], with high probability
(6)∥𝒫Q⊥eiejT∥F≤4plog(mnp)mn.Bernstein’s Inequality [16, 17]. Assume that X1,X2,…,Xn are independent random variables with 𝔼[Xi]=0, for all i. Furthermore, suppose that |Xi|≤M. Then,
(7)ℙ{|∑i‍Xi|>t}≤2exp(-t22∑iVar(Xi)+2Mt/3).Lemma 7.
Ifρ≥logn/mn, then with high probability
(8)∥S∥0≤2ρmn.Proof.
Letωij be the indicator variables with ωij=1 if (ij)∈Ω and ωij=0 for otherwise. For S∈Ω, we have
(9)∥S∥0≤∑ij‍ωij.
Let Yij:=ωij-ρ and Z:=∑ij‍Yij. For 𝔼[Yij]=𝔼[ωij]-ρ=0 and |Yij|≤1, it is obvious that Yij satisfies Bernstein’s inequality. Note that
(10)∑ij‍Var(Yij)=ρ(1-ρ)mn≤ρmn.
According to Bernstein’s inequality, letting t=ρmn, we have
(11)ℙ{|∑ij‍ωij-ρmn|>ρmn}≤2exp(-3ρmn8).
Combining with ρ≥logn/mn, we have
(12)ℙ{|∑ij‍ωij-ρmn|>ρmn}≤n-3/8.
In other words,∥S∥0≤2ρmn with high probability. Note that limn→∞logn/mn=0. That means ρ can obtain very small value when n is very large.Theorem  8(a).Suppose thatSis sparse matrix withSupp(S)~Ber(ρ)andQ⊥is ap-dimensional random subspace ofℝm×n. Ifρ≤δ2/64plog(mnp), with high probability, one has(13)∥𝒫Q⊥S∥F≤δ∥S∥F.Proof.
According to triangle inequality, we have(14)∥𝒫Q⊥S∥F=∥𝒫Q⊥(∑ij‍SijeiejT)∥F≤∑ij‍|Sij|∥𝒫Q⊥eiejT∥F≤4plog(mnp)mn∑ij‍|Sij|≤2ρmn∥S∥F4plog(mnp)mn≤64pρlog(mnp)∥S∥F.
In the third inequality, we have used Lemma 6. In the foarth inequality, we have used Cauchy-Schwarz inequality and Lemma 7. Combining with ρ≤δ2/64plog(mnp), we can obtain
(15)∥𝒫Q⊥S∥F≤δ∥S∥F.Theorem  8(b).Suppose thatSis sparse matrix withSupp(S)~Ber(ρ), andQ⊥is ap-dimensional random subspace ofℝm×n. Ifρ≤δ2/64plog(mnp), with high probability, one has(16)(1-δ)∥S∥F≤∥𝒫QS∥F≤(1+δ)∥S∥F.Proof.
For∥𝒫Q∥≤1, we have ∥𝒫QS∥F≤∥S∥F≤(1+δ)∥S∥F. On the other hand, we have
(17)∥𝒫QS∥F=∥S-𝒫Q⊥S∥F≥∥S∥F-∥𝒫Q⊥S∥F≥(1-δ)∥S∥F.


## 2.2. Bounding the Behavior of∥𝒫Q⊥(L)∥F

Lemma 9 (see [7, 18]).
Suppose thatYd is distributed as a chi-squared random variable with d degrees of freedom. Then, for each t>0(18)ℙ{Yd-d≥t2d+t2}≤e-t2/2,(19)ℙ{Yd≤d(1-ϵ)}≤e-ϵ2d/4.Lemma 10.
With high probability, one has(20)∥H∥F≥12.Proof.
According to the definition ofH, we have
(21)∥H∥F2=∥M∥F2mn,
where (M)ij~𝒩(0.1). It is necessary to bound ∥M∥F2. It is easy to note that ∥M∥F2 is distributed as a chi-squared random variable with mn degrees of freedom. Letting ϵ=3/4, we have
(22)ℙ{Yd≤mn(1-ϵ)}≤e-ϵ2mn/4,
where we have used (19). Equation (22) tells us: ∥M∥F2≥mn/4 with high probability. Therefore, Lemma 9 is established.Lemma 11 (see [8, 9]).
Assume thatΩ~Ber(ρ). If 1-ρ≥Cϵ-2(μrlogn/n), then with high probability
(23)∥𝒫Ω𝒫T∥2≤ρ+ϵ.According to Lemma11, if ϵ and ρ are small enough, we have the below formula with high probability
(24)∥𝒫Ω𝒫T∥≤12.Lemma 12.
Under the assumption of Theorem1, with high probability, one has
(25)∥L∥F+∥S∥F≤5∥M∥F.Proof.
Note thatL∈T, and we have
(26)∥𝒫ΩL∥F2=∥𝒫Ω𝒫TL∥F2≤14∥L∥F2=14(∥𝒫ΩL∥F2+∥𝒫Ω⊥M∥F2).
In the first inequality, we have used Lemma 11. In the second equality, we have used 𝒫Ω⊥L=𝒫Ω⊥M, because S∈Ω. It is obvious that
(27)∥𝒫ΩL∥F≤33∥𝒫Ω⊥M∥F.
Therefore,
(28)∥L∥F≤∥𝒫ΩL∥F+∥𝒫Ω⊥L∥F≤33∥𝒫Ω⊥M∥F+∥𝒫Ω⊥M∥F≤53∥M∥F.
And thus, we can obtain
(29)∥L∥F+∥S∥F=∥L∥F+∥M-L∥F≤2∥L∥F+∥M∥F≤5∥M∥F.
Lemma 12 is established.Next, we will bound the behavior of∥𝒫Q⊥(L)∥F, based on Lemma 9 to Lemma 12.Theorem  13(a).Suppose thatLber-rank matrix andQ⊥is ap-dimensional random subspace ofℝn×n. Ifr≤(mnδ2/12p)-(5/3)log(n), with high probability, one  has(30)∥𝒫Q⊥L∥F≤δ∥L∥F.As pointed out by one reviewer, Lemma 15 in [10] is similar to Theorem  13(a). Lemma 15 in [10] tells us (30) is established if r≤nδ2/pυ; however it is obvious that r is strongly based on υ which is defined as if there exists an orthonormal basis {Gi} for L satisfying maxi∥Gi∥2≤υ/n, which is very difficult to compute. The condition of r in Theorem  13(a) is just based on m,n,p, and δ, which is easy to determine.Proof.
According to the definition ofQ⊥, we have
(31)∥𝒫Q⊥L∥F=∑k=1p‍|〈Gk,L〉|2≤pmaxk|〈Gk,L〉|,
where G1,G2,…,Gk are independent and identically distributed to G mentioned before. According to (31), it is necessary to bound |〈G,L〉|. Suppose that UΣVT is singular value decomposition of matrix L; that is, L=UΣVT=∑l=1r‍σlulvlT. Therefore, according to triangle inequality, we have
(32)|〈G,L〉|≤∑l=1r‍σl|〈G,ulvlT〉|=∑l=1r‍σl|ulTGvl|≤∑l=1r‍σl2∑l=1r‍(ulTGvl)2=∥L∥F∥H∥Fmn∑l=1r‍(ulTMvl)2≤2∥L∥Fmn∑l=1r‍(ulTMvl)2,
where ul,vl are the lth rows of U,V, respectively. In the second inequality, we have used Cauchy-Schwarz inequality. In the last inequality, we have used Lemma 10. Let yl:=ulTMvl=∑ij‍ulimijvlj; note that
(33)𝔼{yl}=∑ij‍ulivlj𝔼{mij}=0,Var{yl}=∑ij‍Var{ulivljmij}=∑ij‍uli2vlj2Var{mij}=1,
where we have used the fact ∑i‍uli2=1 and ∑j‍vlj2=1. In other word yl~𝒩(0,1). Let z:=∑l=1r‍(ulTMvl)2=∑l=1r‍yl2. It is obvious that z is distributed as a chi-squared random variable with r degrees of freedom.
According to Lemma9, letting t=2logn, we can obtain
(34)ℙ(Yd≥d+2logn2d+4logn)≤n-2.
It implies that with high probability
(35)Yd≤d+2logn2d+4logn.
That is, with high probability
(36)z≤r+2logn2r+4logn.
Combining with (31), (32), and (36), with high probability, we can obtain
(37)∥𝒫Q⊥L∥F≤2p∥L∥Fmnr+2logn2r+4logn≤2p∥L∥Fmn3r+5logn,
where we have used the fact: if a,b≥0,2ab≤a+b. Let
(38)2pmn3r+5logn≤δ.
That is,
(39)r≤mnδ212p-53log(n).
Theorem  13(a) is established.Theorem  13(b).Suppose thatLisμ-incoherent matrix andQ⊥is ap-dimensional random subspace ofℝn×n. Ifr≤(mnδ2/12p)-(5/3)log(n), with high probability, one has(40)(1-δ)∥L∥F≤∥𝒫QL∥F≤(1+δ)∥L∥F.Proof.
The main idea of the proof follows the arguments of Theorem  8(b).Proof of Theorem4.
According to Theorems  8 and 13 and the assumption of Lemma3, we have
(41)∥𝒫Q⊥L∥F≤δ∥L∥F,∥𝒫Q⊥S∥F≤δ∥S∥F.
Therefore,
(42)∥𝒫Q⊥(L+S)∥F≤∥𝒫Q⊥L∥F+∥𝒫Q⊥S∥F≤δ(∥L∥F+∥S∥F)≤5δ∥M∥F.
Then,
(43)∥𝒫QM∥F=∥M-𝒫Q⊥M∥F≥∥M∥F-∥𝒫Q⊥M∥F≥(1-5δ)∥M∥F.
Theorem 4 is established.


## 3. Conclusion

In this paper, we address the problem of principal component pursuit with reduced linear measurements (PCP_RLM). In order to obtain an easy handed band ofτ, we prove that operator 𝒫Q obeys RIP with high probability if the low-rank matrix satisfies incoherent conditions and the sparse matrix is enough sparse. And then, based on the RIP of operator 𝒫Q, we provide the bound of parameters depending only on observed quantities. In the future, we will try to analyze the robustness of optimum solution of the strongly convex programming (1) with RIP property.



---

*Source: 959403-2013-05-23.xml*