# Noise Folding in Completely Perturbed Compressed Sensing

Authors: Limin Zhou; Xinxin Niu; Jing Yuan
Journal: Journal of Applied Mathematics
 (2016)

---

## Abstract

This paper first presents a new generally perturbed compressed sensing (CS) modely=(A+E)(x+u)+e, which incorporated a general nonzero perturbation E into sensing matrix A and a noise u into signal x simultaneously based on the standard CS model y=Ax+e and is called noise folding in completely perturbed CS model. Our construction mainly will whiten the new proposed CS model and explore in restricted isometry property (RIP) and coherence of the new CS model under some conditions. Finally, we use OMP to give a numerical simulation which shows that our model is feasible although the recovered value of signal is not exact compared with original signal because of measurement noise e, signal noise u, and perturbation E involved.


---

## Body

## 1. Introduction

Compressed sensing (CS) model, which was proposed by Candes et al. [1] and Donoho [2], had become a hot topic and attracted a lot of researchers to study it over the past years because it can recover a signal as a technique. Thus, it had been widely applied in many areas such as radar systems [3], signal processing [4], and image processing [5]. These applications depended on the main function of CS model to recover the original signal with some related algorithms including convex relaxation [6, 7], greedy pursuit [7], and Bayesian algorithm [8, 9], which were utilized to estimate the best approximation value of the original signal.The classic and basic CS model in an unperturbed scenario and can be formulated as(1)y=Ax.Here, y∈Rm is the measurement vector or observation value and A∈Rm×n is a full rank measurement matrix with m≪n. Signal x∈Rn is k-sparse if no more than k entries of signal x are nonzero. Thus, x is called a k-sparse signal.To date, the basic model has mature theories and there are a lot of different algorithms [6, 7] such as match pursuit (BP) [1, 10], orthogonal match pursuit (OMP) [11–15], Compressive Sampling Matching Pursuit (CoSaMP) [16], and Bayesian algorithm [8, 9], which can be recovered exactly as signal value and utilized in many areas [17–20].But in practice, the measurement vectory in (1) was often contaminated by a noise or an error. More concretely, a noise term e∈Rm, calledan additive noise, was incorporated into y=Ax to result in apartially perturbed model [21–23]:(2)y=Ax+e,where a noise or an error e (e≠0) was uncorrelated with signal x. There were two methods to model noise e in [24]. Here, a noise e was randomly sampled from Gaussian distribution. This model was used in many areas [21–23] and naturally had mature theories in recent years. For example, a number of accuracy algorithms on (2) emerged, for example, BP [1, 21], OMP [21], CoSaMP [16], and Bayesian algorithm [8, 9].In 2010, Herman and Strohmer [25] first incorporated a randomly nontrivial perturbation E into matrix A in (2) to generate ageneral perturbation model [25–27] as follows:(3)y=A+Ex+e,where E∈Rm×n was calleda general perturbation ora multiplicative noise. They studied influence of E on signal x and indicated that considering this CS model was a must [25–27]. Intuitively, it was harder to analyze the multiplicative noise E compared to the additive noise e because E was related to signal x with Ex.As for (3), there were two different scenarios from different points of view [25–27]. First, from user’s point of view, the sensing process can be formulated as follows:(4)y^=Ax+e,A^=A+E.Its recovery process can be expressed by N1x^=y^,A^,….Thus, the useful measurement matrix was the perturbed matrixA^ not the original measurement matrix A. The system was researched on the recovery signal with BP in [16, 25] and OMP in [26, 27].The second model was from designer’s perspective [25–27]. The sensing process was just written as (5)y^=A^x+e,A^=A+Eand the recovery process was written asN1′x^=Ry^,A,….The useful sensing matrix was A not A^ and the observation value was y^. To the best of our knowledge, no work focused on recovery signal in the context of general perturbation E except for [25–27].In some practical scenarios, signal itself was often contaminated by noise and such case was applied in sub-Nyquist converter. Though introducing noise to signal was significant, no prolific paper studied such signal noiseu except for [24] which first added an unknown random noise u∈Rn to sinal x of y=Ax+e to producenoise folding CS model [24]:(6)y=Ax+u+e.They analyzed the RIP and coherence of the equivalent system after whitening and showed that the difference of the RIP and coherence between original A and whitened matrix was small [24]. Based on [24–27], we propose a new CS model and study its related properties in Section 3.


## 2. Preliminaries

In this paper, we will restrict our attention toRIP and coherence of our new CS model. By convention, sensing matrix A and perturbation E are assumed to sample independently and identically distributed (i.i.d.) Gaussian random variables since such matrix satisfies RIP and coherence, and so forth [7, 24], with probability one.Definition 1 (see [7]).
A sensing matrixA satisfies the restricted isometry property (RIP) of order k if there exists δk∈(0,1)s.t.:(7)1-δkx22≤Ax22≤1+δkx22for any k-sparse vector with k=1,2,…, where δk is the smallest nonnegative number called the restricted isometry constant (RIC).Definition 1​′ (see [24]). For (1) and (2), there is another equivalent statement for RIP of A, denoted by RIP′, in some special cases. For any index set Λ⊂{1,…,N} of size k, let AΛ denote the submatrix of A consisting of the column vectors indexed by Λ, and the matrix A possesses RIP′ with constants 0<αk≤βk, if (8)αkh2≤AΛh2≤βkh∀h∈Rkfor any index set Λ⊂{1,…,N} of size k, where N is a positive integer.For (6), there existed another form of RIP for matrix A which was given by Lemma 2 [24] since matrix A was whitened.Lemma 2 (see [24]).
As for folding noise model (6), RIP for whitened A can be formulated as (9)αk1-ρ1h22≤BΛh22≤βk1+ρ1h22,where ρ1=ρ/1-ρ with 0<ρ<1/2 and matrix B was obtained after whitening sensing matrix A.The perturbationE and sensing matrix A in (3) can be quantified below in [25–27] (10)E2A2≤εA,E2kA2k≤εAk,A2k=σmaxkA,where the symbol A2 denotes spectral norm of a matrix A, A2(k) denotes the largest spectral norm taken over all k-column submatrices of matrix A, and σmax(k)(A) [25] denotes the largest nonzero singular value taken over all k-column submatrices of matrix A. It was appropriate to assume 0<εA, εA(k), and εy≪1.Lemma 3 (RIP for A^ [25]).
Fork=1,2,…, given the RIC associated with matrix A in (3) and the relative perturbation εA(k), fix the constant (11)δ^k,max=1+δk1+εAk2-1.Assume that the RIC  δ^k≤δ^k,max for matrix A^=A+E is the smallest nonnegative number, and the RIP for A^ can be written as(12)1-δ^kx22≤A^x22≤1+δ^kx22for any k-sparse vector x.From Lemma3 with (6), there is one equivalent statement for the RIP for A^ in some special cases given by Lemma  3′ [24].Lemma  3′ (see [24]).For any index setΛ⊂{1,…,N}of sizek, letA^Λdenote the submatrix ofA^consisting of the column vectors indexed byΛ. A matrixA^possessesRIPwith constants0<α^k≤β^k,if(13)α^kh2≤A^Λh2≤β^kh,∀h∈Rkfor any index setΛ⊂{1,…,N}of sizek, whereNis a positive integer.Definition 4 (see [7]).
The coherence,μ(A), of a matrix A is the largest absolute inner product between any two columns Ai, Aj, i≠j, of matrix A as follows: (14)μA=max1≤i<j≤n⁡AiTAjAi2Aj2.


## 3. Constructions

### 3.1. A New Completely Perturbed CS Model

As mentioned above, for (2), (3), and (6), only one noise in (2) or two noises in (3) and (6) affected the CS model. Maybe a noise e, a noise u, and a perturbation E simultaneously affect the CS model although no paper studies this. In terms of the idea, [24] together with [25–27] motivate us to introduce a noise u togeneral perturbation model (3) to generatenoise folding in generally perturbed situation or to incorporate a nontrivial perturbation E into (6) to producea complete perturbation CS model with folding noise, which for the first time yields so callednoise folding in completely perturbed CS model. We formulate the CS model as(15)y=A+Ex+u+e,where e∈Rm is a random noise vector with covariance σ2I and u∈Rn presents a random premeasurement noise vector whose covariance is σ02I independent of e. Here e and u are regarded asadditive noise. E∈Rm×n is a random perturbation matrix and more details on perturbation E can be seen in [25]. Here we call CS model (15)noise folding in completely perturbed CS model. Analogous to (3) in [25–27], (15) can also be considered in two different situations. Similarly, from user’s point of view, an incorrect sensing matrix can be obtained via an unknown measurement model: (16)y^=Ax+u+e,A^=A+Eand the recovery process algorithm can be written as N2x^=Ry^,A^,u,….The only difference betweenN1 and N2 is noise u in N2. From the designer’s view, sensing process can be formulated as (17)y^=A^x+u+e,A^=A+Eand its recovery process is as N2′x^=Ry^,A,u,….Similarly, compared toN1′, noise u belongs to N2′. In this paper, we only study simply its properties: RIP and coherence after whitening. Obviously, (15) can be extended to general multiperturbation CS model:(18)y=A+∑i=1nEix+u+e,i=1,2,…,n,where Ei is perturbation. System (18) can be viewed as a generalization of our proposed CS (15), which implies that the general conclusion of (18) can be obtained from the special conclusion of (15). The concrete results can be seen in the next section. Simultaneously, other general CS systems can be conjectured naturally as follows:(19)y=∑i=1sAi+Ex+u+e,y=∑i=1sAi+Ex+∑i=1sui+e,y=∑i=1sAi+∑i=1sEix+∑i=1sui+e.Although their properties seem to be many but we do not know how to exploit and analyze them, we leave them as open problems. Here we mainly study relative RIP and coherence on (15) and (18). In the next section, we give general results.


### 3.2. Problem Formulation

For (15), our goal is to analyze the effect of the premeasurement noise u and E on its RIP and coherence.Throughout this paper, assume thate is a random noise vector with covariance σ2I, and u is a random noise vector with covariance σ02I independent of e. Under these assumptions, (15) will be proved to be equivalent to y=B^x+w, where B^ is a matrix whose coherence and RIP constants are very close to that of A, w is whitened noise with variance (σ2+n/mσ02)I, and I is identity matrix.


### 3.3. Equivalent Formulation

To set up our conclusion, (15) can be expressed as(20)y=A+Ex+w,w=A+Eu+e.By hypothesis of whitened noise, the covariance of effective vectorw is Q:Q=σ2I+σ02(A+E)(A+E)T. Obviously, noise w is not whitened where the recovery process analysis becomes complicated. If w still preserves whitening, one case A^=A+E must be proportional to identity matrix. For example, suppose that A+E consists of r=n/m orthogonal basis such as (21)A=A1+E1,A2+E2,…,Ar+Erin which Ai+Ei, i=1,2,…,r, are m×m orthogonal matrices. Therefore, we have (22)A+EA+ET=A1+E1A1+E1T+⋯+Ar+ErAr+ErT=rI=nmI,where noise covariance of w is Q=γI, γ=σ2+n/mσ02. Under the special case, y=(A+E)(x+u)+e (or y=(A+E)x+w) is equivalent to y=Ax+e. Compared with noise covariance of e, noise covariance of w has increased by γ/σ2. If σ02≈σ2, the noise covariance of w is increased by n/m, which was callednoise folding [24].


### 3.4. RIP and Coherence of Our CS Model

We will show that the conclusion holds generally. In other words, if(A+E)(A+E)T is not proportional to the identity matrix I, (15) and (20) are roughly equivalent really. Now we describe it in detail.Note that ifE is one random matrix, A^=A+E is a random matrix. To study RIP and coherence of A^, we must whiten noise w by multiplying Q1-1/2 with Q1=Q/γ and get the equivalent system: (23)y=B^x+v,s.t.B^=Q1-1/2A+E,v=Q1-1/2w.Note that noise vector v is whitened with covariance matrix γI exactly if (A+E)(A+E)T is proportional to identity matrix. But the biggest difference lies in measurement matrix changing from original matrix A^ to B^ by whitening. The changing range is measured with three important indexes: RIP constant, coherence, and stable. Our theory mainly depends on approximating (A+E)(A+E)T with n/mI and even A^ is an arbitrary matrix. Let (24)η=I-mnA+EA+ET2measure accuracy of the approximating, in which · denotes the standard operator norm in Rn. For derivation convenient, assume that η is very small and show that the coherence and RIP constant of B^ are very close to that of A. By convention, the entries of A are i.i.d. mean zero and variance 1/m random variables with Gaussian distribution; thus, it is easy to justify that η is always small.Another useful formula can be formulated:(25)η0=I-mnAAT2which was introduced in [24]. The fact that η0 was very small had been proved in [24] with restrictions on only matrix A. It is natural to think whether the difference between η and η0 is very small. Theorem 5 confirms our conjecture and further inspires us to think whether the difference between B^’s coherence and RIP and A^’s and A’s is very small, respectively. The later related theorems will give us the positive answers.Theorem5 shows the relation between η0 and η under the context E2/A2≤εA.Theorem 5.
Assume that sensing matrixA∈Rm×n, an unknown random matrix E∈Rm×n, m≪n, E2/A2≤εA, 0<εA≪1, (26)η0=I-mnAAT2,η=I-mnA+EA+ET20<η0<1/2, A=σ1, where σ1 is the largest nonzero positive singular value of A; then (27)η0-mn2εA+εA2σ12≤η≤η0+mn2εA+εA2σ12.Proof.
The detailed proof is postponed to the Appendix.Remark 6.
For (27), by assumption m≪n, n→∞, obtain (28)mn⟶0,mn2εA+εA2σ12⟶0due to 0<εA≪1, a positive number σ1. Thus, η0≤η1≤η0; that is, η0=η, such that m≪n, n→∞, 0<εA≪1 and there is a positive number σ1. Theorem 5 shows the relation between η and η0 which implies that η=η0 under some special conditions. Therefore, we can let η<1/2 like η0<1/2 in [24].Theorem7 shows the RIP of B^ in the case of η<1/2 though 0<η<1 is sufficient for the proof of the RIC for B^.Theorem 7.
Assume that sensing matrixA∈Rm×n, an unknown random matrix E∈Rm×n, m≪n. Let E2/A2≤εA, 0<εA≪1, (29)η=I-mnA+EA+E2,η0=I-mnAAT20<η<1/2, 0<η0<1/2, suppose that A^ satisfies the RIP of order k with 0<α^Λ≤β^Λ, and σ1>0 is the largest singular value of matrix A; then B^ satisfies the RIP of order k with different constants below: (30)α^k1-μ1′h22≤B^Λh22≤β^k1+μ1′h22,μ1′=μ11-μ1α^k1-η1′h22≤B^Λh22≤β^k1+η1′h22,η1′=η11-η1α^k1-μ2′h22≤B^Λh22≤β^k1+μ2′h22,μ2′=μ21-μ2.Proof.
The detailed proof is postponed to the Appendix.Remark 8.
In Theorems5 and 7, the condition E/A≤εA with 0<εA≪1 can be taken in place of E=εA [25], in which E is a simple version of A, so that we can get another result. Due to paper volume, they are omitted here. But their proofs are very simple that researchers can prove them and yield perfect results.Multiperturbation CS system (18) can be viewed as a generalization of the new proposed CS system (15) so that the general conclusion of the (18) can come from that of (15). Theorems 9 and 11 give us the results.Theorem 9.
Assume thatA∈Rm×n is sensing matrix, and Ei∈Rm×n is an unknown random matrix with m≪n. Let (31)η0=I-mnAAT2,η~=I-mnA+∑i=1sEiA+∑i=1sEiT2.Ei2/A2≤εA, 0<εA≪1, and let σ1 be the largest singular value of matrix A, A=σ1; and suppose that matrix A satisfies RIP, a number s is an integer, s<n; then the relation between η~ and η0 can be formulated as (32)η0-mn2sεAσ1+s2εA2σ1≤η~≤η0+mn2sεAσ1+s2εA2σ1.Proof.
The detailed proof is postponed to the Appendix.Remark 10.
For (32), since 1≤s≪n, m≪n, and s, m, n are positive integers and σ1 is a constant, (m/n)(2sεAσ12+s2εA2σ12)→0 when n→∞ which implies η~→η0.Theorem 11.
Assume thatA∈Rm×n is sensing matrix, and Ei∈Rm×n is an unknown random matrix with m≪n. Let (33)η0=mnAAT-I2,η~=I-mnA+∑i=1sEiA+∑i=1sEiT2,Ei2/A2≤εA, and 0<εA≪1, and suppose that η~<1/2, σ1 is the largest singular value of matrix A, s and n are integers, s<n, and (34)Q=σ2I+σ02A+∑i=1sEiA+∑i=1sEiT,γ=σ2+nmσ02,Q1=Qγ;then, (35)α^k1-μ3′h22≤B^Λh22≤β^k1+μ3′h22,μ3′=μ31-μ3α^k1-η3′h22≤B^Λh22≤β^k1+η3′h22,η3′=η31-η3α^k1-μ4′h22≤B^Λh22≤β^k1+μ4′h22,μ4′=μ41-μ4.Proof.
The detailed proof is postponed to the Appendix.Remark 12.
Though0<η~<1 is sufficient for the proof, the RIC for B^ is positive in the restriction of η~<1/2.Next, we compare thecoherence of B^ after whitening A^ to that of A^. Ai, i=1,…,n, is used to denoted the ith column vector of a matrix A. Similar to the coherence of A, the coherence of A^ is first given in Definition 13.Definition 13.
Assume thatA∈Rm×n is a random matrix, E∈Rm×n is an unknown random matrix in CS, and A^=A+E; then coherence of A^, denoted by μ(A^), can be formulated as (36)μA^=max1≤i<j≤n⁡A^iTA^jA^i2A^j2.In fact, μ(A^) is the largest absolute inner product between any columns A^i, A^j, i≠j.As mentioned above,Q1-I<1, respectively, in some special contexts with E2/A2≤εA in Theorem 7. We can take advantage of Q1-I<1 to prove Theorem 14. For the lack of space, we only take Q1-I<μ2, Q1-1-I<μ2′ as an example with η<1/2. The proofs of the rest of the cases, including Q1-I<μ1,η1, and Q1-1-I<μ1′,η1′, are similar, and we leave them to readers. As for the general results μ(A+∑i=1nEi) of the general CS model y=(A+∑i=1nEi)(x+u)+e, we omit them too due to space constrains. The proof of general coherence of Q1-1/2(A+∑i=1nEi) is similar too. Theorem 14 demonstrates the relation between coherence of B^ and that of A^.Theorem 14.
Assume thatμ2<3/4 in Q1-I≤μ2, B^=Q1-1/2A^ with A^=A+E; then, (37)μB^≤1+μ^21-μ^22μA^,where μ^2=(1-μ2)-1/2-1, μ(B^)=max⁡|B^iTB^j|/B^i2B^j2. B^j denotes the jth column vector of whitening matrix B^; A^j denotes the jth column vector of A^; that is, A^j=Aj+Ej.Proof.
The detailed proof is postponed to the Appendix.In [25], E is simply version of random matrix A such as E=εA with 0<ε≪1. The relation between μ(A^) and μ(A) will be seen from Theorem 15 below in the case of E=εA, 0<ε≪1.Theorem 15.
LetA^=A+E, E=εA, 0<ε≪1. The correlation of coherence between A and A^ proceeds as (38)μA^≤1+ε21-ε2μAwith 0<ε≪1.Proof.
The proof of Theorem15 is similar to that of Theorem 14; here we omit it.


## 3.1. A New Completely Perturbed CS Model

As mentioned above, for (2), (3), and (6), only one noise in (2) or two noises in (3) and (6) affected the CS model. Maybe a noise e, a noise u, and a perturbation E simultaneously affect the CS model although no paper studies this. In terms of the idea, [24] together with [25–27] motivate us to introduce a noise u togeneral perturbation model (3) to generatenoise folding in generally perturbed situation or to incorporate a nontrivial perturbation E into (6) to producea complete perturbation CS model with folding noise, which for the first time yields so callednoise folding in completely perturbed CS model. We formulate the CS model as(15)y=A+Ex+u+e,where e∈Rm is a random noise vector with covariance σ2I and u∈Rn presents a random premeasurement noise vector whose covariance is σ02I independent of e. Here e and u are regarded asadditive noise. E∈Rm×n is a random perturbation matrix and more details on perturbation E can be seen in [25]. Here we call CS model (15)noise folding in completely perturbed CS model. Analogous to (3) in [25–27], (15) can also be considered in two different situations. Similarly, from user’s point of view, an incorrect sensing matrix can be obtained via an unknown measurement model: (16)y^=Ax+u+e,A^=A+Eand the recovery process algorithm can be written as N2x^=Ry^,A^,u,….The only difference betweenN1 and N2 is noise u in N2. From the designer’s view, sensing process can be formulated as (17)y^=A^x+u+e,A^=A+Eand its recovery process is as N2′x^=Ry^,A,u,….Similarly, compared toN1′, noise u belongs to N2′. In this paper, we only study simply its properties: RIP and coherence after whitening. Obviously, (15) can be extended to general multiperturbation CS model:(18)y=A+∑i=1nEix+u+e,i=1,2,…,n,where Ei is perturbation. System (18) can be viewed as a generalization of our proposed CS (15), which implies that the general conclusion of (18) can be obtained from the special conclusion of (15). The concrete results can be seen in the next section. Simultaneously, other general CS systems can be conjectured naturally as follows:(19)y=∑i=1sAi+Ex+u+e,y=∑i=1sAi+Ex+∑i=1sui+e,y=∑i=1sAi+∑i=1sEix+∑i=1sui+e.Although their properties seem to be many but we do not know how to exploit and analyze them, we leave them as open problems. Here we mainly study relative RIP and coherence on (15) and (18). In the next section, we give general results.


## 3.2. Problem Formulation

For (15), our goal is to analyze the effect of the premeasurement noise u and E on its RIP and coherence.Throughout this paper, assume thate is a random noise vector with covariance σ2I, and u is a random noise vector with covariance σ02I independent of e. Under these assumptions, (15) will be proved to be equivalent to y=B^x+w, where B^ is a matrix whose coherence and RIP constants are very close to that of A, w is whitened noise with variance (σ2+n/mσ02)I, and I is identity matrix.


## 3.3. Equivalent Formulation

To set up our conclusion, (15) can be expressed as(20)y=A+Ex+w,w=A+Eu+e.By hypothesis of whitened noise, the covariance of effective vectorw is Q:Q=σ2I+σ02(A+E)(A+E)T. Obviously, noise w is not whitened where the recovery process analysis becomes complicated. If w still preserves whitening, one case A^=A+E must be proportional to identity matrix. For example, suppose that A+E consists of r=n/m orthogonal basis such as (21)A=A1+E1,A2+E2,…,Ar+Erin which Ai+Ei, i=1,2,…,r, are m×m orthogonal matrices. Therefore, we have (22)A+EA+ET=A1+E1A1+E1T+⋯+Ar+ErAr+ErT=rI=nmI,where noise covariance of w is Q=γI, γ=σ2+n/mσ02. Under the special case, y=(A+E)(x+u)+e (or y=(A+E)x+w) is equivalent to y=Ax+e. Compared with noise covariance of e, noise covariance of w has increased by γ/σ2. If σ02≈σ2, the noise covariance of w is increased by n/m, which was callednoise folding [24].


## 3.4. RIP and Coherence of Our CS Model

We will show that the conclusion holds generally. In other words, if(A+E)(A+E)T is not proportional to the identity matrix I, (15) and (20) are roughly equivalent really. Now we describe it in detail.Note that ifE is one random matrix, A^=A+E is a random matrix. To study RIP and coherence of A^, we must whiten noise w by multiplying Q1-1/2 with Q1=Q/γ and get the equivalent system: (23)y=B^x+v,s.t.B^=Q1-1/2A+E,v=Q1-1/2w.Note that noise vector v is whitened with covariance matrix γI exactly if (A+E)(A+E)T is proportional to identity matrix. But the biggest difference lies in measurement matrix changing from original matrix A^ to B^ by whitening. The changing range is measured with three important indexes: RIP constant, coherence, and stable. Our theory mainly depends on approximating (A+E)(A+E)T with n/mI and even A^ is an arbitrary matrix. Let (24)η=I-mnA+EA+ET2measure accuracy of the approximating, in which · denotes the standard operator norm in Rn. For derivation convenient, assume that η is very small and show that the coherence and RIP constant of B^ are very close to that of A. By convention, the entries of A are i.i.d. mean zero and variance 1/m random variables with Gaussian distribution; thus, it is easy to justify that η is always small.Another useful formula can be formulated:(25)η0=I-mnAAT2which was introduced in [24]. The fact that η0 was very small had been proved in [24] with restrictions on only matrix A. It is natural to think whether the difference between η and η0 is very small. Theorem 5 confirms our conjecture and further inspires us to think whether the difference between B^’s coherence and RIP and A^’s and A’s is very small, respectively. The later related theorems will give us the positive answers.Theorem5 shows the relation between η0 and η under the context E2/A2≤εA.Theorem 5.
Assume that sensing matrixA∈Rm×n, an unknown random matrix E∈Rm×n, m≪n, E2/A2≤εA, 0<εA≪1, (26)η0=I-mnAAT2,η=I-mnA+EA+ET20<η0<1/2, A=σ1, where σ1 is the largest nonzero positive singular value of A; then (27)η0-mn2εA+εA2σ12≤η≤η0+mn2εA+εA2σ12.Proof.
The detailed proof is postponed to the Appendix.Remark 6.
For (27), by assumption m≪n, n→∞, obtain (28)mn⟶0,mn2εA+εA2σ12⟶0due to 0<εA≪1, a positive number σ1. Thus, η0≤η1≤η0; that is, η0=η, such that m≪n, n→∞, 0<εA≪1 and there is a positive number σ1. Theorem 5 shows the relation between η and η0 which implies that η=η0 under some special conditions. Therefore, we can let η<1/2 like η0<1/2 in [24].Theorem7 shows the RIP of B^ in the case of η<1/2 though 0<η<1 is sufficient for the proof of the RIC for B^.Theorem 7.
Assume that sensing matrixA∈Rm×n, an unknown random matrix E∈Rm×n, m≪n. Let E2/A2≤εA, 0<εA≪1, (29)η=I-mnA+EA+E2,η0=I-mnAAT20<η<1/2, 0<η0<1/2, suppose that A^ satisfies the RIP of order k with 0<α^Λ≤β^Λ, and σ1>0 is the largest singular value of matrix A; then B^ satisfies the RIP of order k with different constants below: (30)α^k1-μ1′h22≤B^Λh22≤β^k1+μ1′h22,μ1′=μ11-μ1α^k1-η1′h22≤B^Λh22≤β^k1+η1′h22,η1′=η11-η1α^k1-μ2′h22≤B^Λh22≤β^k1+μ2′h22,μ2′=μ21-μ2.Proof.
The detailed proof is postponed to the Appendix.Remark 8.
In Theorems5 and 7, the condition E/A≤εA with 0<εA≪1 can be taken in place of E=εA [25], in which E is a simple version of A, so that we can get another result. Due to paper volume, they are omitted here. But their proofs are very simple that researchers can prove them and yield perfect results.Multiperturbation CS system (18) can be viewed as a generalization of the new proposed CS system (15) so that the general conclusion of the (18) can come from that of (15). Theorems 9 and 11 give us the results.Theorem 9.
Assume thatA∈Rm×n is sensing matrix, and Ei∈Rm×n is an unknown random matrix with m≪n. Let (31)η0=I-mnAAT2,η~=I-mnA+∑i=1sEiA+∑i=1sEiT2.Ei2/A2≤εA, 0<εA≪1, and let σ1 be the largest singular value of matrix A, A=σ1; and suppose that matrix A satisfies RIP, a number s is an integer, s<n; then the relation between η~ and η0 can be formulated as (32)η0-mn2sεAσ1+s2εA2σ1≤η~≤η0+mn2sεAσ1+s2εA2σ1.Proof.
The detailed proof is postponed to the Appendix.Remark 10.
For (32), since 1≤s≪n, m≪n, and s, m, n are positive integers and σ1 is a constant, (m/n)(2sεAσ12+s2εA2σ12)→0 when n→∞ which implies η~→η0.Theorem 11.
Assume thatA∈Rm×n is sensing matrix, and Ei∈Rm×n is an unknown random matrix with m≪n. Let (33)η0=mnAAT-I2,η~=I-mnA+∑i=1sEiA+∑i=1sEiT2,Ei2/A2≤εA, and 0<εA≪1, and suppose that η~<1/2, σ1 is the largest singular value of matrix A, s and n are integers, s<n, and (34)Q=σ2I+σ02A+∑i=1sEiA+∑i=1sEiT,γ=σ2+nmσ02,Q1=Qγ;then, (35)α^k1-μ3′h22≤B^Λh22≤β^k1+μ3′h22,μ3′=μ31-μ3α^k1-η3′h22≤B^Λh22≤β^k1+η3′h22,η3′=η31-η3α^k1-μ4′h22≤B^Λh22≤β^k1+μ4′h22,μ4′=μ41-μ4.Proof.
The detailed proof is postponed to the Appendix.Remark 12.
Though0<η~<1 is sufficient for the proof, the RIC for B^ is positive in the restriction of η~<1/2.Next, we compare thecoherence of B^ after whitening A^ to that of A^. Ai, i=1,…,n, is used to denoted the ith column vector of a matrix A. Similar to the coherence of A, the coherence of A^ is first given in Definition 13.Definition 13.
Assume thatA∈Rm×n is a random matrix, E∈Rm×n is an unknown random matrix in CS, and A^=A+E; then coherence of A^, denoted by μ(A^), can be formulated as (36)μA^=max1≤i<j≤n⁡A^iTA^jA^i2A^j2.In fact, μ(A^) is the largest absolute inner product between any columns A^i, A^j, i≠j.As mentioned above,Q1-I<1, respectively, in some special contexts with E2/A2≤εA in Theorem 7. We can take advantage of Q1-I<1 to prove Theorem 14. For the lack of space, we only take Q1-I<μ2, Q1-1-I<μ2′ as an example with η<1/2. The proofs of the rest of the cases, including Q1-I<μ1,η1, and Q1-1-I<μ1′,η1′, are similar, and we leave them to readers. As for the general results μ(A+∑i=1nEi) of the general CS model y=(A+∑i=1nEi)(x+u)+e, we omit them too due to space constrains. The proof of general coherence of Q1-1/2(A+∑i=1nEi) is similar too. Theorem 14 demonstrates the relation between coherence of B^ and that of A^.Theorem 14.
Assume thatμ2<3/4 in Q1-I≤μ2, B^=Q1-1/2A^ with A^=A+E; then, (37)μB^≤1+μ^21-μ^22μA^,where μ^2=(1-μ2)-1/2-1, μ(B^)=max⁡|B^iTB^j|/B^i2B^j2. B^j denotes the jth column vector of whitening matrix B^; A^j denotes the jth column vector of A^; that is, A^j=Aj+Ej.Proof.
The detailed proof is postponed to the Appendix.In [25], E is simply version of random matrix A such as E=εA with 0<ε≪1. The relation between μ(A^) and μ(A) will be seen from Theorem 15 below in the case of E=εA, 0<ε≪1.Theorem 15.
LetA^=A+E, E=εA, 0<ε≪1. The correlation of coherence between A and A^ proceeds as (38)μA^≤1+ε21-ε2μAwith 0<ε≪1.Proof.
The proof of Theorem15 is similar to that of Theorem 14; here we omit it.


## 4. Numerical Experiment

Vertical coordinate (sinusoidal) denotes the degree of recovery signal. Horizontal coordinate denotes time whose unit is seconds. Black line denotes original signal and red line denotes recovery signal.Here we use OMP to give three numerical simulation results which demonstrate that our new proposed generally perturbed CS is feasible. To compare signal recovering with OMP from three figures, signal recovery from measurement noise modely=Ax+e is almost exact because of only noise e in basic CS model y=Ax+e. There are a lot of differences between recovery signal and original signal in both y=(A+E)(x+u)+e and y=A(x+u)+e CS models because there are noises u, E, e in the two CS models. Comparing the change between recovered signal and original signal of Figure 1(b) with that of Figure 1(c), the change of Figure 1(c) is a bit bigger than that of Figure 1(b) because perturbation E is involved in Figure 1(c) (y=(A+E)(x+u)+e) and E is not involved in Figure 1(b) (y=A(x+u)+e), which shows that the different noises E, u, e, have a different impact on signal recovering.Figure 1
(a) Recoverx from y=Ax+e. The error of the recovered signal value and original signal value is 6.4835e-004 by the Euclidean norm which indicates that the recovered signal and original signal are almost the same. (b) Recover x from y=A(x+u)+e. The error of the recovered signal value and the original signal value is 6.2258 by the Euclidean norm which means that the recovered signal and original signal are quite different. (c) Recover x from y=(A+E)(x+u)+e. The error of the recovered signal value and the original signal value is 5.8855 by the Euclidean norm which indicates that the recovered signal is much different from the original signal. Compared with the change (error) between the recovery signal and the original signal in (a), the changes (errors) in (b) and (c) differ little. What is more, comparing the change between the recovery signal and the original signal of (c) with that of (b), the change of (c) is quite a little bigger because E is involved in (c) but E is not involved in (b).
(a) (b) (c)Compared with the change (error) between the recovery signal and the original signal in Figure1(a), the changes (errors) in Figures 1(b) and 1(c) differ little. Namely, the differences between recovered signal and original signal from y=(A+E)(x+u)+e are almost the same as the differences between recovery signal and original signal from y=A(x+u)+e, which indicates that our proposed CS model is feasible.Comparing the change between recovered signal and original signal in Figure1(a), the changes in Figures 1(b) and 1(c) are quite different. The fact shows that OMP is not the best algorithm to recover x from y=(A+E)(x+u)+e and y=A(x+u)+e although OMP is used to recover exact original signal from y=Ax+e. Thus, it is important to search for a powerful algorithm or more algorithms to recover exactly for original sparse signal from y=A(x+u)+e and y=(A+E)(x+u)+e as open problems. And here leave these problems to the interested researchers to exploit them because the paper cannot focus on searching for optimal algorithms to recover exactly original signal from CS models y=A(x+u)+e and y=(A+E)(x+u)+e.


## 5. Conclusion

We first propose a new CS system (15) by introducing a multiplicative noise E, a signal noise u, and an additive noise e into unperturbed CS model (1). We derive RIP and coherence for A^=A+E after whitening (15). As a matter of fact, this paper proves that our proposed completely perturbed CS model (15) equals to the classic CS model (2). The only difference is the changed measurement matrix by incorporating a nontrivial perturbation matrix E to measurement matrix and a nontrivial noise u to signal x. And thus this induces noise variance increased by a factor of n/m so that a tighter upper bound and lower bound of RIC is produced. As for coherence of deformed measurement matrix A^=A+E in CS model (15), the constant is nearly invariant essentially with n/m→0, m,n→∞. Finally, we use OMP to give three figures to recover signal from CS model y=Ax+e, y=A(x+u)+e, y=(A+E)(x+u)+e, respectively. Figures 1(b) and 1(c) in our experiment demonstrate that the change between recovered signal and original signal is much bigger than that in Figure 1(a) which indicates our proposed CS model is feasible and OMP is not fit for recovering signal from y=A(x+u)+e and y=(A+E)(x+u)+e. Thus, we can try to search one optimal algorithm or more algorithms to recover signal exactly from the two CS model although OMP is the best algorithm to recover exactly original signal from y=Ax+e now.


## 6. Future Work

Thanks to the features of our proposed CS model (15), there are many works to do. The change between recovered signal and original signal in Figures 1(a), 1(b), and 1(c) indicates that our proposed CS in this paper is feasible although the differences between the recovery signal and original signal in Figures 1(b) and 1(c) are much bigger with OMP than the differences in Figure 1(a). Thus, an obvious problem is to search one algorithm or more optimal algorithms suitable for y=A(x+u)+e and y=(A+E)(x+u)+e to recover signal exactly.The relatedRIP of E in [24] further motivates us to think that E as a perturbation sensing matrix could form one perturbed CS model as y1=E(x+u)+e. Thus, (15) may consist of two similar systems y2=A(x+u)+e and y1=E(x+u)+e. Similarly, our model may be divided into another two models y3=(A+E)x+e, y4=(A+E)u+e, or three basic parts y1′=Ax+e, y2′=Au+e, and y3′=E(x+u)+e. If possible, what can we do to reduce or eliminate the influence of an error CS system y3′=E(x+u)+e? Can we recover signal x from the error system y3′=E(x+u)+e? And if can, how to do it? Maybe there exists CS models y=A(x+u) and y=(A+E)(x+u). In addition, maybe we can also consider the impulse noise and use e+I instead of e where I is the impulse noise. If so, maybe it can generalize our model and we can get very good results in impulse noise model. Here we cannot study such impulse noise model and leave it as an open problem, too.These open problems are worth considering and are to be waited for studying in future work. This paper only does some elementary researches on our proposed CS and we hope that the idea and simple study in this paper will be helpful to study its wide application in the future. We hope that higher level compressed sensing model will be put forward and more and more people explore this areas in the future.



---

*Source: 5094239-2016-03-30.xml*