Nonconvex Relaxation Approaches to Robust Matrix Recovery Shun Wang and Dehua Liu and Zhihua Zhang
College of Computer Science&Technology
Zhejiang University
Hangzhou,China310027
{wss,dehua,zhzhang}@zju.edu
Abstract
Motivated by the recent developments of non-
convex penalties in sparsity modeling,we pro-
po a nonconvex optimization model for hand-
ing the low-rank matrix recovery problem.Dif-
ferent from the famous robust principal com-
ponent analysis(RPCA),we suggest recovering
low-rank and spar matrices via a nonconvex
loss function and a nonconvex penalty.The ad-
vantage of the nonconvex approach lies in its
stronger robustness.To solve the model,we devi
a majorization-minimization augmented Lagrange
multiplier(MM-ALM)algorithm whichfinds the
local optimal solutions of the propod 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 demon-
strate the superiority of our nonconvex approach
over RPCA in terms of matrix recovery accuracy.
1Introduction
In many computer vision and machine learning problems,a data matrix can be reprented as a low-rank component plus a spar component.For example,video surveillance is the superposition of low-rank background and spar foreground; corrupted images can be approximated by low-rank images plus spar data nois;collaborativefiltering problems can be solved by recovering a low-rank rating matrix and a spar noi matrix from a partially obrved data matrix.Therefore, it is of great interest to recover the low-rank component and the spar component from the obrved data matrix.How-ever,solving matrix recovery problems is not trivial.
An intuitive idea is to formulate matrix recovery as a minimization problem with ,the number of nonzero entries)loss and matrix rank penalty.Unfortunately, this optimization problem is NP-hard.An important al-ternative,well-known as robust principal component analy-sis(RPCA)[Cand`
村晚诗意
e s et al.,2011;Wright et al.,2009],re-laxes this problem into minimizing matrix 1-norm loss and nuclear-norm penalty.This alternative is tractable becau the resulting optimization problem is convex.When the rank of the underlying low-rank matrix is sufficiently low,RPCA can exactly recover the low-rank and spar matrices with high probability[Cand`e s et al.,2011].
RPCA has become an effective tool for computer vision applications.Beyond decomposing a data matrix into a low-rank component and a spar component,RPCA can also be reformulated to handle a variety of computer vision problems, and it achieved state of the art results.For example,Liu et al. extended RPCA to solve subspace clustering problems;Peng formulated RPCA to align images;Zhang et al.in-troduced a variant of RPCA to camera calibration problems; Cheng sorted to RPCA for solving image gmen-tation problems;Wang and Zhang employed RPCA to solve colorization problems.
However,RPCA has two major limitations.First,the rank of the underlying low-rank component is not sufficiently low in many applications,which violates the assumptions of RPCA.For example,natural images cannot be effectively ap-proximated by matrices with very low rank,so RPCA may not be an effective tool for image inpainting.Under such a circumstance RPCA has relatively low performance as veri-fied by our experiments.
Second,RPCA does not have good performance in robust dimensionality reduction.As was mentioned in[Wright et al.,2009;Cand`e s et al.,2011],RPCA eks to overcome the brittleness of the conventional PCA when the data are grossly corrupted.Unfortunately,the performance of RPCA in di-mensionality reduction has neither theoretical guarantee nor experiment verification.Unlike truncated singular value de-composition(SVD)which discards only the small singular values,RPCA shrinks all the singular values equally.As is discusd in the following paragraphs,such behavior of RPCA hurts the“good”singular values and thereby leads to biad results.The empirical results in Figure1(b)1(c)1(d) verify this point.
Since RPCA is an important tool in computer vision and machine learning,fundamental improvements in RPCA methodology can significantly contribute to many real world applications.This work eks to better recover the low-rank and spar matrices via a more robust and less bi-ad formulation.Our method is motivated by the non-convex sparsity-inducing penalties in[Fan and Li,2001; Zhang,2010a].Figure1demonstrates that our method ful-fills matrix recovery and dimensionality reduction much more effectively than RPCA.
(a)
obrved(b)rank
200(c)rank
vivo铃声100(d)rank
50(e)rank
200(f)rank
100(g)rank50
Figure1:Results on matrix dimenionality deduction.1(a)a color image with50%entries added with Gaussian nois i.i.d. from N(0,0.12);1(b)1(c)1(d)are the low-rank components recovered from1(a)by RPCA,each of which is of rank200,100, and50,respectively.1(e)1(f)1(g)are recovered by our method(NRMR).
Fan and Li pointed out that the 1-norm penalty over-penalizes large entries of vectors.Moreover,they propod three criteria for good penalty functions:unbiadness,spar-sity and continuity at the origin.The 1-norm satisfies both sparsity and continuity,but it is biad.Bad on the three properties,Fan and Li propod a new penalty func-tion called the smoothly clipped absolute deviation penalty (SCAD).Recently,Zhang proved that a so-called minmax concave plus(MCP)penalty also posss the three proper-ties and achieves better performance than SCAD.Both SCAD and MCP are nonconvex and nearly unbiad.Extensive ex-periments in[Breheny and Huang,2011;Fan and Li,2001; Zhang,2010a;Shi et al.,2011;Zhang et al.,2012;Zhang and Tu,2012]have demonstrated the superiority of SCAD and MCP over the 1-norm penalty.
It is a well known fact that the matrix rank is the number of nonzero singular values of a matrix,and t
he nuclear norm is the sum of all the singular values of a matrix.We can thereby relate the matrix rank to the 0-norm of a vector;in the same way we relate the matrix nuclear norm to the 1-norm of a vector.On one hand,this relation implies that the nuclear norm over-penalizes large singular values in the same way that the 1-norm over-penalizes large entries;in other words, the nuclear norm results in a biad estimator as well as the 1-norm does.On the other hand,this relation encourages us to devi a new nonconvex loss function or penalty for dealing with bias in the rank-minimization problems[Mazumder et al.,2010].
In particular,we consider the natural extension of MCP functions on matrices.Moreover,we also propo and study a matrixγ-norm as a nonconvex relaxation of the matrix rank. Roughly speaking,the matrixγ-norm is the minimax concave (MCP)function of the matrix singular values.Theγ-norm is characterized by a positive factor(sayγ),and it is tighter to the matrix rank than the nuclear norm is.Moreover,its limit atγ→∞is the nuclear norm.
We apply the matrix MCP function as a nonconvex relax-ation of the 0-norm loss and the matrixγ-norm as a non-convex relaxation of the matrix rank penalty to handle robust matrix recovery.Our work offers the following contributions.•We introduce the nonconvex sparsity-inducing penalty MCP function to the rank-minimization problem.
•We develop the Nonconvex relaxation bad Robust Ma-trix Recovery(NRMR)model for the matrix recov-ery problem.NRMR alleviates over-penalization on “good”variables and thus better recovers the low-rank and spar matrices.
•We devi a majorization-minimization augmented La-grange multiplier algorithm(MM-ALM)to solve the NRMR model.We also propo a speedup strategy which solves NRMR as efficiently as the ALM algo-rithm solves RPCA.
The remainder of this paper is organized as follows.In Sec-tion3we formulate the matrix recovery problem.In Section4 we apply MCP function to rank-minimization problems and obtain a calledγ-norm with which we formulate the NRMR model.In Section5we devi an algorithm called MM-ALM to solve the NRMR model.In Section6we empirically eval-uate the performance of NRMR mainly in comparison with RPCA.
2Notation
The notations in this paper are defined as follows.For a ma-trix A=[A ij]∈R m×n,let A 0be the ,the number of nonzero entries of A), A 1=
i,j
|A ij|be the 1-norm, A F=(
i,j
A2ij)1/2=(
r
i=1
σ2i(A))1/2be the Frobenius norm,and A ∗=
r
i=1
σi(A)be the nu-clear norm,whereσi(A)be the i-th largest singular value of A and r=min{m,n}.Finally,let I denote the identity ma-trix with appropriate size,1n=[1,1,···,1]T∈R n denote the all-one vector.
3Problem Formulation
Given an m×n matrix D,we are concerned with the prob-lem of recovering a low-rank matrix L and a spar matrix S such that L+S=D.It can be formulated as the following optimization problem:
min
L,S
rank(L)+λ S L+S=D.(1)
Since the problem in(1)is NP-hard,it is intractable in prac-tical applications.Bad on the fact that L ∗and S 1are
the best convex approximations of rank(L)and S 0,respec-tively,Cand`e s et al.propod the RPCA model,which is de-fined by
min
L,S
L ∗+λ S L+S=D.(2)
An efficient algorithm of solving RPCA is an augmented Lagrange multiplier algorithm(ALM),which was studied in[Lin et al.,2009].Like other algorithms for a penalized nuclear norm minimization problem,the ALM algorithm is bad on the singular value shrinkage operator[Cai et al., 2010].
4Methodology
In Section4.1we introduce a nonconvex function that called the matrix MCP norm.In Section4.2we apply MCP to the rank minimization problem and obtained a nonconvex low-rank-inducing penalty called theγ-norm.With the ma-trix MCP norm and theγ-norm,in Section4.3we formu-late the Nonconvex relaxation bad Robust Matrix Recovery (NRMR)model.In Section4.4we discuss how to tune the parameters of NRMR.
4.1The Matrix MCP Norm
Given a vectorβ=(β1,...,βp)T∈R p,λ>0,andγ>0, the MCP function[Zhang,2010a]is defined by
Mλ,γ(β)=
p
i=1
ψλ,γ(βi),
where
ψλ,γ(t)=λ
t
1−x/(γλ)
+
dx=
γλ2/2if|t|≥γλ,
λ|t|−t2
2γ
otherwi.
接着造句
Here(z)+=max{z,0}.The matrix MCP norm is naturally defined by
Mλ,γ(A)=
i,j
ψλ,γ(A i,j).(3)
Here and later,we denoteψγ(t)=ψ1,γ(t)and Mγ(A)= M1,γ(A)for notational simplicity.The function Mγ(·)is γ.Whenγ→∞,ψγ(t)→|t|and Mγ(·) becomes the 1-norm;whenγ→0+,it gives ri to a hard threshold operator corresponding to the 0norm.Thus, Mγ(·)bridges the 1and 0norm.The matrix MCP norm enjoys veral properties as follows.
Proposition1.The matrix MCP norm defined in(3)satisfies the following properties:
(1)Mγ(A)≥0,with equality iff A=0;
(2)Mγ(A)is A|,where|A|=
|A ij|
;
(3)Mγ(A)is increasing inγ,Mγ(A)≤ A 1,and
limγ→∞Mγ(A)= A 1.
It is worth pointing out that like the matrix rank and the 0-norm,the matrix MCP norm and the following matrixγ-norm are not real norms,becau they are nonconvex and do not satisfy the triangle inequality of a norm.4.2The Matrixγ-Norm
Letσ(A)=
σ1(A),...,σr(A)
T
be a function from R m×n to R r+where r=min{m,n}.Interestingly,we have that rank(A)= σ(A) 0, A ∗= σ(A) 1,and A F= σ(A) 2.This can help us better understand the connection between the vector 1-norm and the matrix nu-clear norm.
Fan and Li(2001)and Zhang(2010)proved that the 1-norm over-penalizes large components,leading t
o a biad estimator.Moreover,they showed that a nonconvex penalty such as SCAD and MCP yields an asymptotically unbiad estimator.This motivates us to apply the MCP function to the rank minimization problem to better approximate the matrix rank.We refer to this nonconvex function as the matrixγ-norm and denote it by A γ.
Particularly,theγ-norm of an m×n matrix A is defined by
A γ:=
r
i=1
σi(A)
1−
u
γ
+
du
=
r
i=1
ψ1,γ
σi(A)
=Mγ
σ(A)
,γ>0.
Clearly, A γis A.Moreover,it is easy to verify that it posss the following properties. Proposition2.Forγ∈(1,∞),then
(1) A γ≥0,with equality iff A=0;
(2) A γis an increasing function ofγ, A γ≤ A ∗,
and limγ→+∞= A ∗;
(3) A γis unitarily invariant;that is, UA V γ= A γ
whenever U(m×m)and V(n×n)are orthonormal.
4.3Formulation of NRMR
We u the matrix MCP norm as a surrogate of the 0-norm and theγ-norm as a surrogate of the matrix rank,simultane-ously.Accordingly,we have
min
L,S
f(L,S)= L γ
1
+λMγ
2
(S);s.t.L+S=D,(4)
where L γ
1
and Mγ
2
(S)are characterized by parametersγ1 andγ2,respectively.Since our model is bad on the idea of nonconvex relaxation,we call it Nonconvex relaxation bad Robust Matrix Recovery(NRMR).From the properties of the matrix MCP norm and theγ-norm,it is clear that NRMR is a tighter approximation to Problem1than RPCA.
4.4The Tuning Parameters
Finally,compared with RPCA which has only one tuning parameterλ,NRMR appears to be more complicated.It is therefore uful to discuss how to tune the parametersλ,γ1andγ2.The parameterλis the most significant among the three parameters and should be carefully chon.Simi-lar to RPCA,λshould be lected from the neighborhood of 1/
max{m,n}.Smallerλgives ri to lower rank of L∗. As forγ1andγ2,experiments show that the results are inn-sitive to them in a large range,butγ1andγ2should be neither
too large nor too small.When γ→+∞,NRMR simply be-comes RPCA;when γ→0+,the local convergence results in poor solutions.Empirically speaking,γ1and γ2should be t to be small real numbers strictly greater than 0.We fix γ1=γ2=4in our experiments.
5Algorithms
This ction is organized as follows:in Sections 5.1we dis-cuss the generalized singular value shrinkage operator for the
γ-norm;in Section 5.2we prent the MM-ALM algorithm for solving NRMR;in Section 5.3we give a more efficient algorithm which is bad on MM-ALM.
5.1
Generalized Singular Value Shrinkage Operator
The Singular Value Threshold (SVT)algorithm is propod in [Cai et al.,2010]for solving the nuclear norm penalized problems.For τ≥0,the singular value shrinkage operator S τis defined by
S τ(X )
=U X D τ(ΣX )V T
X ,
where
D τ(A )
ij
=
sgn(A ij ) |A ij |−τ
+,
(5)
where X =U X ΣX V T
X is the singular value decomposition (SVD)of X .Similarly,we define the generalized singular value shrinkage operator S τ,Λand generalized shrinkage op-erator D τ,W by
S τ,Λ(X )=U X D τ,Λ(ΣX )V T
X ,where
D τ,W (A ) ij
=
sgn(A ij ) |A ij |−τW ij
+.
(6)
Here Λand W are arbitrary elementwi nonnegative ma-trices.The optimality of S τ,Λand D τ,W is shown in Theo-rem 3.Theorem 3.For each τ≥0,γ>0,X ,Y ,X old ∈R m ×n ,let Λ= I −ΣX old /γ +,W = 1m 1T n −|X old |/γ +,then S τ,Λand D τ,W defined in (6)obey
S τ,Λ(Y )=argmin X
12 X −Y 2F +τQ γ σ(X ) σ(X old
) ,
D τ,W (Y )
=
argmin X
12 X −Y 2
F +τQ γ X X
old ,where
Q γ(A |A old )=M γ(A old )+ i,j
(1−|A old ij |/γ)+(|A ij |−|A old
ij |).
is the locally linear approximation (LLA)of M γ(A )given A old .
5.2The MM-ALM Algorithm
The majorization-minimization (MM)method in [Hunter and Li,2005]is a family of algorithms such as the locally quadratic approximation algorithm (LQA)in [Fan and Li,2001],the locally linear approximation algorithm (LLA)in [Zou and Li,2008;Zhang,2010b ],etc.Many optimiza-tion problems with nonconvex penalties can be solved by ho in [Fan and Li,2001;Zou and Li,2008;Zhang,2010a;2010b ].MM proceeds by iteratively solving a
Algorithm 1NRMR via MM-ALM Algorithm
1:Input:Obrvation D ∈R m ×n ,parameters λ,γ1,γ2.
2:Initialize Y (0),L ∗0,S ∗
0;µ>0;k =0;3:repeat
4:L (0)k +1←L ∗k ;S (0)
k +1←S ∗k ;5:Λ←Diag 1n −σ(L ∗k )/γ1 +;
6:W ← 1m 1T n −|S ∗
k |/γ2 +;7:repeat
8:L (j +1)k +1←S 1/µ,Λ D −S (j )
k +1+Y (j )/µ ;
9:S (j +1)k +1←D λ/µ,W D −L (j +1)
k +1+Y (j )/µ ;
10:Y (j +1)←Y (j )+µ D −L (j +1)k +1−S (j +1)k +1
;11:j ←j +1;12:until converged
13:L ∗k +1←L (j +1)k +1;S ∗
k +1←S (j +1)k +1;k ←k +1;14:until converged
15:return L ∗k +1,S ∗
k +1.
convex problem which locally approximates the original non-convex problem in each step.
Our MM-ALM algorithm is a kind of the MM method.MM-ALM consists of an outer loop and an inner loop.In each iteration,the outer loop replaces the nonconvex problem by its LLA to form a weighted RPCA,while the inner loop is an ALM algorithm solving the resulting weighted RPCA problem.MM-ALM repeats the two loops until converged.MM-ALM is described in Algorithm 1.
LLA bad outer loop
The outer loop is bad on LLA.The basic idea is shown in the following proposition which indicates that the LLA ma-jorizes the original problem.
Proposition 4.Let p (x )be a concave function on (0,∞).Then
p (x )≤p (x 0)+p (x 0)(x −x 0),(7)
with equality if x =x 0.
Since the objective function f (L ,S )in Problem 4is (σ(L ),|S |),in each step we approximate L γ1+λM γ2(S )by its LLA at (σ(L old ),|S old |)and obtain the fol-lowing problem:
min
L ,S
Q γ1 σ(L ) σ(L old
) +λQ γ2 S
S
old ;s .t .L +S =D ,
(8)
which majorizes the NRMR problem in (4).The problem above is indeed a weighted RPCA.Thus we can resort to the ALM algorithm in [Lin et al.,2009],which solves RPCA,to solve Problem 8.
The ALM algorithm bad inner loop
We employ the ALM algorithm to solve Problem 8.The aug-mented Lagrangian function is
L µ L ,S ,Y L old ,S old =Q γ1 σ(L ) σ(L old )
+λQ γ2 S S old + Y ,D −L −S +µ
D −L −S 2F .
The ALM algorithm solves Problem 8by alternately mini-mizing L µL and S ,and Y ;each step is guaranteed by Theorem 3.This constitutes the inner loop of MM-ALM.
Local Convergence
According to Proposition4and the properties of the ALM al-gorithm,we have that the objective function values of Prob-lem4in each iteration of Algorithm1obey
f(L∗k+1,S∗k+1)≤Qγ
1
σ(L∗k+1)
σ(L∗k)
+λQγ
2
S∗k+1
S∗k
≤Qγ
1
σ(L∗k)
σ(L∗k)
+λQγ
2
S∗k
S∗k
=f(L∗k,S∗k).
Thus the objective function value is monotonically nonin-creasing.If we denote the optimal low rank matrix by L∗and spar matrix by S∗,then(L∗,S∗)is afixed point of Algo-rithm1,that is,if we denote(L k+1,S k+1)=N(L k,S k), then we have(L∗,S∗)=N(L∗,S∗).
Though the convergence is local,local optimal solutions are still effective.The empirical results in[Breheny and Huang,2011;Fan and Li,2001;Shi et al.,2011;Zhang, 2010a;Zhang et al.,2012;Gong et al.,2012;Xiang et al., 2012]all show that the local optimal solutions to the non-convex problems usually outperform global optimal solution to the LASSO[Tibshirani,1996]problem.In Section6we will
empirically demonstrate that the local optimal solutions to NRMR are superior over the global optimal solutions to RPCA.
5.3Speedup Strategy for MM-ALM
As we e,each step of the MM procure results in a weighted RPCA;the MM-ALM algorithm repeatedly calls the ALM algorithm to solve the weighted RPCA problem in the inner loop.Thus the computation costs can be many times more than the ALM algorithm solving RPCA.To alleviate the com-putations,we propo an efficient strategy.
A feasible strategy is the one-step LLA studied in[Zou and Li,2008].The one-step LLA runs the outer loop only once instead of waiting to converge.In comparison,Algorithm1is actually the multi-stage LLA in[Zhang,2010b].Here we u the solutions to RPCA for initialization.Our off-line exper-iments reveal that the full MM-ALM leads to only marginal improvement over one-step LLA by sacrificing much more time.Experiments show that one-step LLA at most doubles the time of the ALM algorithm for solving RPCA.
6Experiments
In this ction,we conduct experiments mainly in compari-son with RPCA,which is the state-of-the-art low-rank matrix recovery method.Though there are veral nonconvex ap-proaches such as log-det heuristic[Fazel et al.,2003],Matrix ALPS[Kyrillidis and Cevher,2012],and SpaRCS[Waters et al.,2011],none of them were claimed to outperform RPCA in terms of accuracy,so we do not compare with the non-convex methods.
In our experiments,RPCA is solved by the ALM algorithm in[Lin et al.,2009],and our NRMR is solved by the one-step LLA algorithm;we do not u the full MM-ALM algorithm becau it is time consuming.Wefixγ1=γ2=4for NRMR in all the following experiments.We u the relative square error(RSE)to evaluate matrix recovery accuracy.The RSE
Figure2:Results on the50test images,each contaminated with i.i.d.Gaussian nois or salt-pepper nois.On average, RCPA conducts39.0times SVD,while NRMR conducts72.5 times SVD.
is defined as follows:
RSE= L∗−L F/ L F,(9) where L∗is the solution to RPCA or NRMR,and L is the ground truth.We u the number of singular value decompo-sitions(SVD)to evaluate time efficiency,becau the running time of all the aforementioned algorithms are dominated by the SVD in each iteration.
In Section6.1we conduct experiments on a t of syn-thetic data.In Section6.2we conduct experiments on natural image for the sake of prenting and comparing the results intuitively.
Table1:Comparisons between RPCA and NRMR on the syn-thetic data
rank(L)RSE#SVD rank(L∗) (r)RPCA NRMR RPCA NRMR RPCA NRMR
m=500, S 0=0.05m2
508.58×10−78.29×10−721405050
1007.94×10−79.97×10−72968100100
1503.30×10−27.39×10−53672419153
2000.1650.1193673471475
m=500, S 0=0.2m2
501.68×10−32.91×10−632606150
1000.2780.1673470282195
1500.4600.3943473328259
繁花落幕2000.5500.5363473325266 6.1Synthetic Data
Wefirst compare between RPCA and NRMR on a t of syn-thetic data.The data are generated in the following way.We
个人简历文字版
缅桂花
(a)
original(b)
noisy(c)
RPCA(d)
NRMR(e)
RPCA(f)NRMR
Figure3:Denoising results on images with Gaussian nois.3(a)original images;3(b)noisy images;3(c)and3(d)are obtained by tuningλsuch that the RSEs are minimized;3(e)and3(f)are of the same rank(rank(L∗)=100).
generate L as a product of two m×r matrices who entries
are sampled i.i.d.from Gaussian distribution N(0,1/m).The
spar component S is constructed by tting a proportion of
entries to be±1and the rest to be zeros.Then we u RPCA
and NRMR to recover the low-rank and spar components
from the data matrix D=L+S.We tune the parame-
tersλof both RPCA and NRMR and report the results where
RSE is minimized.We report the RSE,number of SVD,and
rank(L∗)in Table1.
6.2Natural Images
We u50images from the Berkeley Segmentation
Datat[Martin et al.,2001].Each image consists of three
components:L red,L green,L blue∈R m×n,each entry of
which takes value in[0,1).Our off-line experiments show
that direct concatenation of the three components to a matrix
leads to better results than gmenting the image into patches
followed by concatenating the patches.So we directly stack
the three components into an m×3n matrix L:
L=[L red,L green,L blue]∈R m×3n.(10)
Then we add nois to L to generate contaminated data ma-
trix D.We add two kinds of nois:i.i.d.Gaussian nois
N(0,0.22)to50%pixels of the images,or salt and pepper
nois to20%pixels.
For both RPCA and NRMR,we tune the parameterλthat
班级名称the recovered low-rank matrix has a rank of rank(L∗)=100.
We report the resulting RSE and average number of SVD in
Figure2.We also give in Figure3some visual comparisons
among the recovered low-rank matrices,whereλis tuned
such that RSE is minimized or that rank(L∗)=100.
We can e from Table1and Figure2that the local optimal
of NRMR always outperforms the global optimal of RPCA
(in terms of RSE),without adding much computation costs.
The recovered images in Figure3all demonstrate that the
results of our NRMR better approximate the original images.
7Concluding Remarks
In this paper we have propod a novel approach to the ma-
trix recovery problem.In particular,we have defined robust
matrix recovery as an optimization problem with a noncon-
vex loss function and a nonconvex penalty function.We
have also devid a majorization-minimization augmented
Lagrange multiplier algorithm for solving this nonconvex
problem.Experiment results demonstrate that our noncon-
vex approach significantly outperforms RPCA—a classical
convex approach—in terms of accuracy without much extra
computation cost.
Our work has shed light on some important properties of
古代爱情the nonconvex low-rank-inducing penalty.The matrixγ-
norm studied in this paper is a tighter approximation to the
matrix rank than the nuclear norm is,and it broadens our
vision on matrix low-rank learning—from a convex relax-
ation to a more general nonconvex relaxation.Furthermore,
it might be interesting to further explore theγ-norm as well
as other potential nonconvex low-rank-inducing penalties to
better solve the low-rank matrix learning problem.
Acknowledgments
This work has been supported in part by the Natural Science
Foundations of China(No.61070239)and the Scholarship
Award for Excellent Doctoral Student granted by Ministry of
Education.
