In this paper, we propose a non-convex formulation to recover the authentic structure from the corrupted real data. Typically, the specific structure is assumed to be low rank, which holds for a wide range of data, such as images and videos. Meanwhile, the corruption is assumed to be sparse. In the literature, such a problem is known as Robust Principal Component Analysis (RPCA), which usually recovers the low rank structure by approximating the rank function with a nuclear norm and penalizing the error by an 1-norm. Although RPCA is a convex formulation and can be solved effectively, the introduced norms are not tight approximations, which may cause the solution to deviate from the authentic one. Therefore, we consider here a non-convex relaxation, consisting of a Schatten-p norm and an q-norm that promote low rank and sparsity respectively. We derive a proximal iteratively reweighted algorithm (PIRA) to solve the problem. Our algorithm is based on an alternating direction method of multipliers, where in each iteration we linearize the underlying objective function that allows us to have a closed form solution. We demonstrate that solutions produced by the linearized approximation always converge and have a tighter approximation than the convex counterpart. Experimental results on benchmarks show encouraging results of our approach.
There are several works aimed at improving the low-rank and sparse matrix recovery. @cite_10 proposed an Accelerated RPCA using random projection. Zhou and Tao @cite_12 developed a fast solver for low-rank and sparse matrix recovery with hard constraints on both @math and @math . To alleviate the challenges raised by coherent data, most recently, recovered the coherent data by Low-Rank Representation (LRR) @cite_7 . developed a fast first-order algorithm to solve the SPCP problem @cite_1 . Fazel suggested to reformulating the rank optimization problem as a Semi-Definite Programming (SDP) problem @cite_15 . An accelerated proximal gradient optimization technique was applied to solve the nuclear norm regularized least squares @cite_14 @cite_32 .
@cite_14 @cite_7 @cite_1 @cite_32 @cite_15 @cite_10 @cite_12
1977580401 2175634846 2072356364 2214177029
Recovering low-rank and sparse matrices from incomplete or corrupted observations is an important problem in statistics, machine learning, computer vision, as well as signal and image processing. In theory, this problem can be solved by the natural convex joint mixed relaxations (i.e., l 1 -norm and trace norm) under certain conditions. However, all current provable algorithms suffer from superlinear per-iteration cost, which severely limits their applicability to large-scale problems. In this paper, we propose a scalable, provable and structured robust bilinear factorization (RBF) method to recover low-rank and sparse matrices from missing and grossly corrupted data, i.e., robust matrix completion (RMC), or incomplete and grossly corrupted measurements, i.e., compressive principal component pursuit (CPCP). Specifically, we first present two small-scale matrix trace norm regularized bilinear factorization models for RMC and CPCP problems, in which repetitively calculating SVD of a large-scale matrix is replaced by updating two much smaller factor matrices. Then, we apply the alternating direction method of multipliers (ADMM) to efficiently solve the RMC problems. Finally, we provide the convergence analysis of our algorithm, and extend it to address general CPCP problems. Experimental results verified both the efficiency and effectiveness of our method compared with the state-of-the-art methods. Numerous applications in data mining and machinelearning require recovering a matrix of minimal rank. Robust principal component analysis (RPCA) is a generalframework for handling this kind of problems. Nuclear normbased convex surrogate of the rank function in RPCA iswidely investigated. Under certain assumptions, it can recoverthe 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 byadding all singular values together, which is essentially a '1-norm of the singular values, the resulting approximation erroris not trivial and thus the resulting matrix estimator canbe significantly biased. To seek a closer approximation andto alleviate the above-mentioned limitations of the nuclearnorm, we propose a nonconvex rank approximation. Thisapproximation to the matrix rank is tighter than the nuclearnorm. To solve the associated nonconvex minimization problem, we develop an efficient augmented Lagrange multiplier basedoptimization algorithm. Experimental results demonstrate thatour method outperforms current state-of-the-art algorithms inboth accuracy and efficiency. Low-rank matrix recovery from a corrupted observation has many applications in computer vision. Conventional methods address this problem by iterating between nuclear norm minimization and sparsity minimization. However, iterative nuclear norm minimization is computationally prohibitive for large-scale data (e.g., video) analysis. In this paper, we propose a Robust Orthogonal Subspace Learning (ROSL) method to achieve efficient low-rank recovery. Our intuition is a novel rank measure on the low-rank matrix that imposes the group sparsity of its coefficients under orthonormal subspace. We present an efficient sparse coding algorithm to minimize this rank measure and recover the low-rank matrix at quadratic complexity of the matrix size. We give theoretical proof to validate that this rank measure is lower bounded by nuclear norm and it has the same global minimum as the latter. To further accelerate ROSL to linear complexity, we also describe a faster version (ROSL+) empowered by random sampling. Our extensive experiments demonstrate that both ROSL and ROSL+ provide superior efficiency against the state-of-the-art methods at the same level of recovery accuracy. Motivated by the recent developments of nonconvex penalties in sparsity modeling, we propose a nonconvex optimization model for handing the low-rank matrix recovery problem. Different from the famous robust principal component analysis (RPCA), we suggest recovering low-rank and sparse matrices via a nonconvex loss function and a nonconvex penalty. The advantage of the nonconvex approach lies in its stronger robustness. To solve the model, we devise a majorization-minimization augmented Lagrange multiplier (MM-ALM) algorithm which finds the local optimal solutions of the proposed nonconvex model. We also provide an efficient strategy to speedup MM-ALM, which makes the running time comparable with the state-of-the-art algorithm of solving RPCA. Finally, empirical results demonstrate the superiority of our nonconvex approach over RPCA in terms of matrix recovery accuracy.