Robust PCA via Nonconvex Rank Approximation
Numerous applications in data mining and machine learning require recovering a matrix of minimal rank. Robust principal component analysis (RPCA) is a general framework for handling this kind of problems. Nuclear norm based convex surrogate of the rank function in RPCA is widely investigated. Under certain assumptions, it can recover the underlying true low rank matrix with high probability. However, those assumptions may not hold in real-world applications. Since the nuclear norm approximates the rank by adding all singular values together, which is essentially a $\ell_1$-norm of the singular values, the resulting approximation error is not trivial and thus the resulting matrix estimator can be significantly biased. To seek a closer approximation and to alleviate the above-mentioned limitations of the nuclear norm, we propose a nonconvex rank approximation. This approximation to the matrix rank is tighter than the nuclear norm. To solve the associated nonconvex minimization problem, we develop an efficient augmented Lagrange multiplier based optimization algorithm. Experimental results demonstrate that our method outperforms current state-of-the-art algorithms in both accuracy and efficiency.
Code (1)
Similar Papers 제목 키워드 기반
Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA
This work studies low-rank approximation of a positive semidefinite matrix from partial entries via nonconvex optimization. We characterized how well local-minimum based low-rank factorization approximates a fixed positi…
ClusteringDimensionality ReductionMatrix CompletionGeneralized Nonconvex Approach for Low-Tubal-Rank Tensor Recovery
The tensor-tensor product-induced tensor nuclear norm (t-TNN) (Lu et al., 2020) minimization for low-tubal-rank tensor recovery attracts broad attention recently. However, minimizing the t-TNN faces some drawbacks. For e…
Image InpaintingLow-Rank Matrix CompletionNonconvex Robust High-Order Tensor Completion Using Randomized Low-Rank Approximation
Within the tensor singular value decomposition (T-SVD) framework, existing robust low-rank tensor completion approaches have made great achievements in various areas of science and engineering. Nevertheless, these method…
Computational EfficiencyEnhanced nonconvex low-rank approximation of tensor multi-modes for tensor completion
Higher-order low-rank tensor arises in many data processing applications and has attracted great interests. Inspired by low-rank approximation theory, researchers have proposed a series of effective tensor completion met…
Robust Subspace Clustering via Tighter Rank Approximation
Matrix rank minimization problem is in general NP-hard. The nuclear norm is used to substitute the rank function in many recent studies. Nevertheless, the nuclear norm approximation adds all singular values together and …
ClusteringFace ClusteringMotion Segmentation