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.

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.

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.

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.

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.

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.

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 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.

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.

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.