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.

Accelerated Matrix Recovery via Random Projection Based on Inexact Augmented Lagrange Multiplier Method

In this paper, a unified matrix recovery model was proposed for diverse corrupted matrices. Resulting from the separable structure of the proposed model, the convex optimization problem can be solved efficiently by adopting an inexact augmented Lagrange multiplier (IALM) method. Additionally, a random projection accelerated technique (IALM+RP) was adopted to improve the success rate. From the preliminary numerical comparisons, it was indicated that for the standard robust principal component analysis (PCA) problem, IALM+RP was at least two to six times faster than IALM with an insignificant reduction in accuracy; and for the outlier pursuit (OP) problem, IALM+RP was at least 6.9 times faster, even up to 8.3 times faster when the size of matrix was 2 000×2 000.

Improved nonconvex optimization model for low-rank matrix recovery

Low-rank matrix recovery is an important problem extensively studied in machine learning, data mining and computer vision communities. A novel method is proposed for low-rank matrix recovery, targeting at higher recovery accuracy and stronger theoretical guarantee. Specifically, the proposed method is based on a nonconvex optimization model, by solving the low-rank matrix which can be recovered from the noisy observation. To solve the model, an effective algorithm is derived by minimizing over the variables alternately. It is proved theoretically that this algorithm has stronger theoretical guarantee than the existing work. In natural image denoising experiments, the proposed method achieves lower recovery error than the two compared methods. The proposed low-rank matrix recovery method is also applied to solve two real-world problems, i.e., removing noise from verification code and removing watermark from images, in which the images recovered by the proposed method are less noisy than those of the two compared methods.

Proximity point algorithm for low-rank matrix recovery from sparse noise corrupted data

The method of recovering a low-rank matrix with an unknown fraction whose entries are arbitrarily corrupted is known as the robust principal component analysis （RPCA）. This RPCA problem, under some conditions, can be exactly solved via convex optimization by minimizing a combination of the nuclear norm and the 11 norm. In this paper, an algorithm based on the Douglas-Rachford splitting method is proposed for solving the RPCA problem. First, the convex optimization problem is solved by canceling the constraint of the variables, and ~hen the proximity operators of the objective function are computed alternately. The new algorithm can exactly recover the low-rank and sparse components simultaneously, and it is proved to be convergent. Numerical simulations demonstrate the practical utility of the proposed algorithm.

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.

Pairwise constraint propagation via low-rank matrix recovery

As a kind of weaker supervisory information, pairwise constraints can be exploited to guide the data analysis process, such as data clustering. This paper formulates pairwise constraint propagation, which aims to predict the large quantity of unknown constraints from scarce known constraints, as a low-rank matrix recovery(LMR) problem. Although recent advances in transductive learning based on matrix completion can be directly adopted to solve this problem, our work intends to develop a more general low-rank matrix recovery solution for pairwise constraint propagation, which not only completes the unknown entries in the constraint matrix but also removes the noise from the data matrix. The problem can be effectively solved using an augmented Lagrange multiplier method. Experimental results on constrained clustering tasks based on the propagated pairwise constraints have shown that our method can obtain more stable results than state-of-the-art algorithms,and outperform them.

Robust signal recovery algorithm for structured perturbation compressive sensing

It is understood that the sparse signal recovery with a standard compressive sensing（CS） strategy requires the measurement matrix known as a priori. The measurement matrix is, however, often perturbed in a practical application.In order to handle such a case, an optimization problem by exploiting the sparsity characteristics of both the perturbations and signals is formulated. An algorithm named as the sparse perturbation signal recovery algorithm（SPSRA） is then proposed to solve the formulated optimization problem. The analytical results show that our SPSRA can simultaneously recover the signal and perturbation vectors by an alternative iteration way, while the convergence of the SPSRA is also analytically given and guaranteed. Moreover, the support patterns of the sparse signal and structured perturbation shown are the same and can be exploited to improve the estimation accuracy and reduce the computation complexity of the algorithm. The numerical simulation results verify the effectiveness of analytical ones.

Using shapes correlation for active contour segmentation of uterine fibroid ultrasound images in computer-aided therapy

Segmenting the lesion regions from the ultrasound （US） images is an important step in the intra-operative planning of some computer-aided therapies. High-Intensity Focused Ultrasound （HIFU）, as a popular computer-aided therapy, has been widely used in the treatment of uterine fibroids. However, such segmentation in HIFU remains challenge for two reasons： （1） the blurry or missing boundaries of lesion regions in the HIFU images and （2） the deformation of uterine fibroids caused by the patient＇s breathing or an external force during the US imaging process, which can lead to complex shapes of lesion regions. These factors have prevented classical active contour-based segmentation methods from yielding desired results for uterine fibroids in US images. In this paper, a novel active contour-based segmentation method is proposed, which utilizes the correlation information of target shapes among a sequence of images as prior knowledge to aid the existing active contour method. This prior knowledge can be interpreted as a unsupervised clustering of shapes prior modeling. Meanwhile, it is also proved that the shapes correlation has the low-rank property in a linear space, and the theory of matrix recovery is used as an effective tool to impose the proposed prior on an existing active contour model. Finally, an accurate method is developed to solve the proposed model by using the Augmented Lagrange Multiplier （ALM）. Experimental results from both synthetic and clinical uterine fibroids US image sequences demonstrate that the proposed method can consistently improve the performance of active contour models and increase the robustness against missing or misleading boundaries, and can greatly improve the efficiency of HIFU therapy.

Stable recovery of low-rank matrix via nonconvex Schatten p-minimization

In this paper, a sufficient condition is obtained to ensure the stable recovery(ε≠ 0) or exact recovery(ε = 0) of all r-rank matrices X ∈ Rm×nfrom b = A(X) + z via nonconvex Schatten p-minimization for anyδ4r∈ [3～(1/2))2, 1). Moreover, we determine the range of parameter p with any given δ4r∈ [(3～(1/2))/22, 1). In fact, for any given δ4r∈ [3～(1/2))2, 1), p ∈(0, 2(1- δ4r)] suffices for the stable recovery or exact recovery of all r-rank matrices.

Study of Array Antenna Pattern Synthesis Based on Sparse Sensing

Aiming at the problem that a large number of array elements are needed for uniform arrays to meet the requirements of direction map,a sparse array pattern synthesis method is proposed in this paper based on the sparse sensing theory.First,the Orthogonal Matching Pursuit(OMP)algorithm and the Exact Augmented Lagrange Multiplier(EALM)algorithm were improved in the sparse sensing theory to obtain a more efficient Orthogonal Multi⁃Matching Pursuit(OMMP)algorithm and the Semi⁃Exact Augmented Lagrange Multiplier(SEALM)algorithm.Then,the two improved algorithms were applied to linear array and planar array pattern syntheses respectively.Results showed that the improved algorithms could achieve the required pattern with very few elements.Numerical simulations verified the effectiveness and superiority of the two synthetic methods.In addition,compared with the existing sparse array synthesis method,the proposed method was more robust and accurate,and could maintain the advantage of easy implementation.

The bounds of restricted isometry constants for low rank matrices recovery

This paper discusses conditions under which the solution of linear system with minimal Schatten-p norm, 0 〈 p ≤ 1, is also the lowest-rank solution of this linear system. To study this problem, an important tool is the restricted isometry constant （RIC）. Some papers provided the upper bounds of RIC to guarantee that the nuclear-norm minimization stably recovers a low-rank matrix. For example, Fazel improved the upper bounds to δ4Ar 〈 0.558 and δ3rA 〈 0.4721, respectively. Recently, the upper bounds of RIC can be improved to δ2rA 〈 0.307. In fact, by using some methods, the upper bounds of RIC can be improved to δ2tA 〈 0.4931 and δrA 〈 0.309. In this paper, we focus on the lower bounds of RIC, we show that there exists linear maps A with δ2rA 〉1√2 or δrA 〉 1/3 for which nuclear norm recovery fail on some matrix with rank at most r. These results indicate that there is only a little limited room for improving the upper bounds for δ2rA and δrA.Furthermore, we also discuss the upper bound of restricted isometry constant associated with linear maps A for Schatten p （0 〈 p 〈 1） quasi norm minimization problem.

Robust PCA for Ground Moving Target Indication in Wide-Area Surveillance Radar System

Robust PCA has found important applications in many areas,such as video surveillance,face recognition,latent semantic indexing and so on.In this paper,we study its application in ground moving target indication(GMTI)in wide-area surveillance radar system.MTI is the key task in wide-area surveillance radar system.Due to its great importance in future reconnaissance systems,it attracts great interest from scientists.In(Yan et al.in IEEE Geosci.Remote Sens.Lett.,10:617–621,2013),the authors first introduced robust PCA to model the GMTI problem,and demonstrate promising simulation results to verify the advantages over other models.However,the robust PCA model can not fully describe the problem.As pointed out in(Yan et al.in IEEE Geosci.Remote Sens.Lett.,10:617–621,2013),due to the special structure of the sparse matrix(which includes the moving target information),there will be difficulties for the exact extraction of moving targets.This motivates our work in this paper where we will detail the GMTI problem,explore the mathematical properties and discuss how to set up better models to solve the problem.We propose two models,the structured RPCA model and the row-modulus RPCA model,both of which will better fit the problem and take more use of the special structure of the sparse matrix.Simulation results confirm the improvement of the proposed models over the one in(Yan et al.in IEEE Geosci.Remote Sens.Lett.,10:617–621,2013).

Adaptive sparse and dense hybrid representation with nonconvex optimization

Sparse representation has been widely used in signal processing,pattern recognition and computer vision etc.Excellent achievements have been made in both theoretical researches and practical applications.However,there are two limitations on the application of classification.One is that sufficient training samples are required for each class,and the other is that samples should be uncorrupted.In order to alleviate above problems,a sparse and dense hybrid representation(SDR)framework has been proposed,where the training dictionary is decomposed into a class-specific dictionary and a non-class-specific dictionary.SDR putsℓ1 constraint on the coefficients of class-specific dictionary.Nevertheless,it over-emphasizes the sparsity and overlooks the correlation information in class-specific dictionary,which may lead to poor classification results.To overcome this disadvantage,an adaptive sparse and dense hybrid representation with non-convex optimization(ASDR-NO)is proposed in this paper.The trace norm is adopted in class-specific dictionary,which is different from general approaches.By doing so,the dictionary structure becomes adaptive and the representation ability of the dictionary will be improved.Meanwhile,a non-convex surrogate is used to approximate the rank function in dictionary decomposition in order to avoid a suboptimal solution of the original rank minimization,which can be solved by iteratively reweighted nuclear norm(IRNN)algorithm.Extensive experiments conducted on benchmark data sets have verified the effectiveness and advancement of the proposed algorithm compared with the state-of-the-art sparse representation methods.

SOLVING SYSTEMS OF QUADRATIC EQUATIONS VIA EXPONENTIAL-TYPE GRADIENT DESCENT ALGORITHM

We consider the rank minimization problem from quadratic measurements,i.e.,recovering a rank r matrix X 2 Rn×r from m scalar measurements yi=ai XX⊤ai,ai 2 Rn,i=1,...,m.Such problem arises in a variety of applications such as quadratic regression and quantum state tomography.We present a novel algorithm,which is termed exponential-type gradient descent algorithm,to minimize a non-convex objective function f(U)=14m Pm i=1(yi−a⊤i UU⊤ai)2.This algorithm starts with a careful initialization,and then refines this initial guess by iteratively applying exponential-type gradient descent.Particularly,we can obtain a good initial guess of X as long as the number of Gaussian random measurements is O(nr),and our iteration algorithm can converge linearly to the true X(up to an orthogonal matrix)with m=O(nr log(cr))Gaussian random measurements。