Robustness of orthogonal matching pursuit under restricted isometry property

Orthogonal matching pursuit （OMP） algorithm is an efficient method for the recovery of a sparse signal in compressed sensing, due to its ease implementation and low complexity. In this paper, the robustness of the OMP algorithm under the restricted isometry property （RIP） is presented. It is shown that 5K＋V/KOK,1 〈 1 is sufficient for the OMP algorithm to recover exactly the support of arbitrary /（-sparse signal if its nonzero components are large enough for both 12 bounded and lz~ bounded noises.

Analysis of orthogonal multi-matching pursuit under restricted isometry property

Orthogonal multi-matching pursuit（OMMP）is a natural extension of orthogonal matching pursuit（OMP）in the sense that N（N≥1）indices are selected per iteration instead of 1.In this paper,the theoretical performance of OMMP under the restricted isometry property（RIP）is presented.We demonstrate that OMMP can exactly recover any K-sparse signal from fewer observations y=φx,provided that the sampling matrixφsatisfiesδKN-N＋1＋√K/NθKN-N＋1,N〈1.Moreover,the performance of OMMP for support recovery from noisy observations is also discussed.It is shown that,for l_2 bounded and l_∞bounded noisy cases,OMMP can recover the true support of any K-sparse signal under conditions on the restricted isometry property of the sampling matrixφand the minimum magnitude of the nonzero components of the signal.

A Perturbation Analysis of Low-Rank Matrix Recovery by Schatten p-Minimization

A number of previous papers have studied the problem of recovering low-rank matrices with noise, further combining the noisy and perturbed cases, we propose a nonconvex Schatten p-norm minimization method to deal with the recovery of fully perturbed low-rank matrices. By utilizing the p-null space property (p-NSP) and the p-restricted isometry property (p-RIP) of the matrix, sufficient conditions to ensure that the stable and accurate reconstruction for low-rank matrix in the case of full perturbation are derived, and two upper bound recovery error estimation ns are given. These estimations are characterized by two vital aspects, one involving the best r-approximation error and the other concerning the overall noise. Specifically, this paper obtains two new error upper bounds based on the fact that p-RIP and p-NSP are able to recover accurately and stably low-rank matrix, and to some extent improve the conditions corresponding to RIP.

AN ADAPTIVE MEASUREMENT SCHEME BASED ON COMPRESSED SENSING FOR WIDEBAND SPECTRUM DETECTION IN COGNITIVE WSN

An Adaptive Measurement Scheme (AMS) is investigated with Compressed Sensing (CS) theory in Cognitive Wireless Sensor Network (C-WSN). Local sensing information is collected via energy detection with Analog-to-Information Converter (AIC) at massive cognitive sensors, and sparse representation is considered with the exploration of spatial temporal correlation structure of detected signals. Adaptive measurement matrix is designed in AMS, which is based on maximum energy subset selection. Energy subset is calculated with sparse transformation of sensing information, and maximum energy subset is selected as the row vector of adaptive measurement matrix. In addition, the measurement matrix is constructed by orthogonalization of those selected row vectors, which also satisfies the Restricted Isometry Property (RIP) in CS theory. Orthogonal Matching Pursuit (OMP) reconstruction algorithm is implemented at sink node to recover original information. Simulation results are performed with the comparison of Random Measurement Scheme (RMS). It is revealed that, signal reconstruction effect based on AMS is superior to conventional RMS Gaussian measurement. Moreover, AMS has better detection performance than RMS at lower compression rate region, and it is suitable for large-scale C-WSN wideband spectrum sensing.

A NEW SUFFICIENT CONDITION FOR SPARSE RECOVERY WITH MULTIPLE ORTHOGONAL LEAST SQUARES

A greedy algorithm used for the recovery of sparse signals,multiple orthogonal least squares(MOLS)have recently attracted quite a big of attention.In this paper,we consider the number of iterations required for the MOLS algorithm for recovery of a K-sparse signal x∈R^(n).We show that MOLS provides stable reconstruction of all K-sparse signals x from y=Ax+w in|6K/ M|iterations when the matrix A satisfies the restricted isometry property(RIP)with isometry constantδ_(7K)≤0.094.Compared with the existing results,our sufficient condition is not related to the sparsity level K.

Some Results for Exact Support Recovery of Block Joint Sparse Matrix via Block Multiple Measurement Vectors Algorithm

Block multiple measurement vectors (BMMV) is a reconstruction algorithm that can be used to recover the support of block K-joint sparse matrix X from Y = ΨX + V. In this paper, we propose a sufficient condition for accurate support recovery of the block K-joint sparse matrix via the BMMV algorithm in the noisy case. Furthermore, we show the optimality of the condition we proposed in the absence of noise when the problem reduces to single measurement vector case.

Compressed Data Separation via ℓ_(q)-Split Analysis with ℓ_(∞)-Constraint

In this paper,we study compressed data separation(CDS)problem,i.e.,sparse data separation from a few linear random measurements.We propose the nonconvex ℓ_(q)-split analysis with ℓ_(∞)-constraint and 0<q≤1.We call the algorithm ℓ_(q)-split-analysis Dantzig selector(ℓ_(q)-split-analysis DS).We show that the two distinct subcomponents that are approximately sparse in terms of two different dictionaries could be stably approximated via the ℓ_(q)-split-analysis DS,provided that the measurement matrix satisfies either a classical D-RIP(Restricted Isometry Property with respect to Dictionaries and ℓ_(2) norm)or a relatively new(D,q)-RIP(RIP with respect to Dictionaries and ℓ_(q)-quasi norm)condition and the two different dictionaries satisfy a mutual coherence condition between them.For the Gaussian random measurements,the measurement number needed for the(D,q)-RIP condition is far less than those needed for the D-RIP condition and the(D,1)-RIP condition when q is small enough.

STABLE RECOVERY OF SPARSELY CORRUPTED SIGNALS THROUGH JUSTICE PURSUIT DE-NOISING

This paper considers a corrupted compressed sensing problem and is devoted to recover signals that are approximately sparse in some general dictionary but corrupted by a combination of interference having a sparse representation in a second general dictionary and measurement noise.We provide new restricted isometry property(RIP)analysis to achieve stable recovery of sparsely corrupted signals through Justice Pursuit De-Noising(JPDN)with an additional parameter.Our main tool is to adapt a crucial sparse decomposition technique to the analysis of the Justice Pursuit method.The proposed RIP condition improves the existing representative results.Numerical simulations are provided to verify the reliability of the JPDN model.

A sharp recovery condition for block sparse signals by block orthogonal multi-matching pursuit

We consider the block orthogonal multi-matching pursuit(BOMMP) algorithm for the recovery of block sparse signals.A sharp condition is obtained for the exact reconstruction of block K-sparse signals via the BOMMP algorithm in the noiseless case,based on the block restricted isometry constant(block-RIC).Moreover,we show that the sharp condition combining with an extra condition on the minimum l_2 norm of nonzero blocks of block K-sparse signals is sufficient to ensure the BOMMP algorithm selects at least one true block index at each iteration until all true block indices are selected in the noisy case.The significance of the results we obtain in this paper lies in the fact that making explicit use of block sparsity of block sparse signals can achieve better recovery performance than ignoring the additional structure in the problem as being in the conventional sense.

On the l_(1)-Norm Invariant Convex k-Sparse Decomposition of Signals

Inspired by an interesting idea of Cai and Zhang,we formulate and prove the convex k-sparse decomposition of vectors that is invariant with respect to the l_(1) norm.This result fits well in discussing compressed sensing problems under the Restricted Isometry property,but we believe it also has independent interest.As an application,a simple derivation of the RIP recovery conditionδk+θk,k<1 is presented.

Convergence analysis of projected gradient descent for Schatten-p nonconvex matrix recovery

The matrix rank minimization problem arises in many engineering applications. As this problem is NP-hard, a nonconvex relaxation of matrix rank minimization, called the Schatten-p quasi-norm minimization(0 < p < 1), has been developed to approximate the rank function closely. We study the performance of projected gradient descent algorithm for solving the Schatten-p quasi-norm minimization(0 < p < 1) problem.Based on the matrix restricted isometry property(M-RIP), we give the convergence guarantee and error bound for this algorithm and show that the algorithm is robust to noise with an exponential convergence rate.

Underwater sonar target imaging via compressed sensing with M sequences

Due to the low sound propagation speed, the tradeoff between high azimuth resolution and wide imaging swath has severely limited the application of sonar underwater target imaging. However, based on compressed sensing(CS) technique, it is feasible to image targets with merely one pulse and thus avoid the above tradeoff. To investigate the possible waveforms for CS-based underwater imaging, the deterministic M sequences widely used in sonar applications are introduced in this paper. By analyzing the compressive matrix constructed from M sequences, the coherence parameter and the restricted isometry property(RIP) of the matrix are derived. Also, the feasibility and advances of M sequence are demonstrated by being compared with the existing Alltop sequence in underwater CS imaging framework. Finally, the results of numerical simulations and a real experiment are provided to reveal the effectiveness of the proposed signal.

Segment-sliding reconstruction of pulsed radar echoes with sub-Nyquist sampling

It has been shown that analog-to-information conversion(AIC) is an efficient scheme to perform sub-Nyquist sampling of pulsed radar echoes. However, it is often impractical, if not infeasible, to reconstruct full-range Nyquist samples because of huge storage and computational load requirements. Based on the analyses of AIC measurement system, this paper develops a novel segment-sliding reconstruction(Seg SR) scheme to effectively reconstruct the Nyquist samples. The Seg SR performs segment-by-segment reconstruction in a sliding mode and can be implemented in real time. An important characteristic that distinguishes the proposed Seg SR from existing methods is that the measurement matrix in each segment satisfies the restricted isometry property(RIP) condition. Partial support in the previous segment can be incorporated into the estimation of the Nyquist samples in the current segment. The effect of interference introduced from adjacent segments is theoretically analyzed, and it is revealed that the interference consists of two interference levels with different impacts to the signal reconstruction performance. With these observations, a two-step orthogonal matching pursuit(OMP)procedure is proposed for segment reconstruction, which takes into account different interference levels and partially known support of the previous segment. The proposed Seg SR scheme achieves near-optimal reconstruction performance with a significant reduction of computational loads and storage requirements. Theoretical analyses and simulations verify its effectiveness.

Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms

Iterative hard thresholding(IHT)and compressive sampling matching pursuit(CoSaMP)are two mainstream compressed sensing algorithms using the hard thresholding operator.The guaranteed performance of the two algorithms for signal recovery was mainly analyzed in terms of the restricted isometry property(RIP)of sensing matrices.At present,the best known bound using the RIP of order 3k for guaranteed performance of IHT(with the unit stepsize)isδ3k<1/√3≈0.5774,and the bound for CoSaMP using the RIP of order 4k isδ4k<0.4782.A fundamental question in this area is whether such theoretical results can be further improved.The purpose of this paper is to affirmatively answer this question and to rigorously show that the abovementioned RIP bound for guaranteed performance of IHT can be significantly improved toδ3k<(√5−1)/2≈0.618,and the bound for CoSaMP can be improved toδ4k<0.5102.

Robustness properties of dimensionality reduction with Gaussian random matrices

In this paper, motivated by the results in compressive phase retrieval, we study the robustness properties of dimensionality reduction with Gaussian random matrices having arbitrarily erased rows. We first study the robustness property against erasure for the almost norm preservation property of Gaussian random matrices by obtaining the optimal estimate of the erasure ratio for a small given norm distortion rate. As a consequence, we establish the robustness property of Johnson-Lindenstrauss lemma and the robustness property of restricted isometry property with corruption for Gaussian random matrices. Secondly, we obtain a sharp estimate for the optimal lower and upper bounds of norm distortion rates of Gaussian random matrices under a given erasure ratio. This allows us to establish the strong restricted isometry property with the almost optimal restricted isometry property(RIP) constants, which plays a central role in the study of phaseless compressed sensing. As a byproduct of our results, we also establish the robustness property of Gaussian random finite frames under erasure.

STABLE AND ROBUST RECOVERY OF APPROXIMATELY k-SPARSE SIGNALS WITH PARTIAL SUPPORT INFORMATION IN NOISE SETTINGS VIA WEIGHTED ℓ_(p)(0

In the existing work,the recovery of strictly k-sparse signals with partial support information was derived in theℓ2 bounded noise setting.In this paper,the recovery of approximately k-sparse signals with partial support information in two noise settings is investigated via weightedℓp(0<p≤1)minimization method.The restricted isometry constant(RIC)conditionδt k<1 pη2 p−1+1 on the measurement matrix for some t∈[1+2−p 2+pσ,2]is proved to be sufficient to guarantee the stable and robust recovery of signals under sparsity defect in noisy cases.Herein,σ∈[0,1]is a parameter related to the prior support information of the original signal,andη≥0 is determined by p,t andσ.The new results not only improve the recent work in[17],but also include the optimal results by weightedℓ1 minimization or by standardℓp minimization as special cases.

Newton-Type Optimal Thresholding Algorithms for Sparse Optimization Problems

Sparse signals can be possibly reconstructed by an algorithm which merges a traditional nonlinear optimization method and a certain thresholding technique.Different from existing thresholding methods,a novel thresholding technique referred to as the optimal k-thresholding was recently proposed by Zhao(SIAM J Optim 30(1):31-55,2020).This technique simultaneously performs the minimization of an error metric for the problem and thresholding of the iterates generated by the classic gradient method.In this paper,we propose the so-called Newton-type optimal k-thresholding(NTOT)algorithm which is motivated by the appreciable performance of both Newton-type methods and the optimal k-thresholding technique for signal recovery.The guaranteed performance(including convergence)of the proposed algorithms is shown in terms of suitable choices of the algorithmic parameters and the restricted isometry property(RIP)of the sensing matrix which has been widely used in the analysis of compressive sensing algorithms.The simulation results based on synthetic signals indicate that the proposed algorithms are stable and efficient for signal recovery.

Weighted ■_(p)-Minimization for Sparse Signal Recovery under Arbitrary Support Prior

Weighted ■_(p)(0<p<l)minimization has been extensively studied as an effective way to reconstruct a sparse signal from compressively sampled measurements when some prior support information of the signal is available.In this paper,we consider the recovery guarantees of Κ-sparse signals via the weighted ■_(p)(0<P<1)minimization when arbitrarily many support priors are given.Our analysis enables an extension to existing works that assume only a single support prior is used.

REQUIRED NUMBER OF ITERATIONS FOR SPARSE SIGNAL RECOVERY VIA ORTHOGONAL LEAST SQUARES

In countless applications,we need to reconstruct a K-sparse signal x∈R n from noisy measurements y=Φx+v,whereΦ∈R^(m×n)is a sensing matrix and v∈R m is a noise vector.Orthogonal least squares(OLS),which selects at each step the column that results in the most significant decrease in the residual power,is one of the most popular sparse recovery algorithms.In this paper,we investigate the number of iterations required for recovering x with the OLS algorithm.We show that OLS provides a stable reconstruction of all K-sparse signals x in[2.8K]iterations provided thatΦsatisfies the restricted isometry property(RIP).Our result provides a better recovery bound and fewer number of required iterations than those proposed by Foucart in 2013.

A Gradient-Enhanced ℓ_(1)Approach for the Recovery of Sparse Trigonometric Polynomials

In this paper,we discuss a gradient-enhancedℓ_(1)approach for the recovery of sparse Fourier expansions.By gradient-enhanced approaches we mean that the directional derivatives along given vectors are utilized to improve the sparse approximations.We first consider the case where both the function values and the directional derivatives at sampling points are known.We show that,under some mild conditions,the inclusion of the derivatives information can indeed decrease the coherence of measurementmatrix,and thus leads to the improved the sparse recovery conditions of theℓ_(1)minimization.We also consider the case where either the function values or the directional derivatives are known at the sampling points,in which we present a sufficient condition under which the measurement matrix satisfies RIP,provided that the samples are distributed according to the uniform measure.This result shows that the derivatives information plays a similar role as that of the function values.Several numerical examples are presented to support the theoretical statements.Potential applications to function(Hermite-type)interpolations and uncertainty quantification are also discussed.