Robust-Subspace-Segmentation-Via-Low-Rank-Represen

1432IEEETRANSACTIONSONCYBERNETICS,VOL.44,NO.8,AUGUST2014RobustSubspaceSegmentationViaLow-RankRepresentationJinhuiChenandJianYangAbstract—Recentlythelow-rankrepresentation(LRR)hasbeensuccessfullyusedinexploringthemultiplesubspacestruc-turesofdata.Itassumesthattheobserveddataisdrawnfromseverallow-ranksubspacesandsometimescontaminatedbyoutliersandocclusions.However,thenoise(low-rankrep-resentationresidual)isassumedtobesparse,whichisgener-allycharacterizedbyminimizingthel1-normoftheresidual.ThisactuallyassumesthattheresidualfollowstheLaplaciandistribution.TheLaplacianassumption,however,maynotbeaccurateenoughtodescribevariousnoisesinrealscenarios.Inthispaper,weproposeanewframework,termedrobustlow-rankrepresentation,byconsideringthelow-rankrepresentationasalow-rankconstrainedestimationfortheerrorsintheobserveddata.Thisframeworkaimstofindthemaximumlikelihoodestimationsolutionofthelow-rankrepresentationresiduals.Wepresentanefficientiterativelyreweightedinexactaug-mentedLagrangemultiplieralgorithmtosolvethenewproblem.Extensiveexperimentalresultsshowthatourframeworkismorerobusttovariousnoises(illumination,occlusion,etc)thanLRR,andalsooutperformsotherstate-of-the-artmethods.IndexTerms—Low-rankrepresentation,matrixrecovery,robustregression,subspacesegmentation.I.IntroductionWITHTHEwidespreadapplicationsincomputervisionandpatternrecognition,subspacemodelisattractingmoreandmoreattentions.Subspacehasbeensuccessfullyusedtodescribeseveraltypesofvisualdata,includingmotion[1]–[3],face[4],[5],andtexture[6].Theconventionaltech-niqueprincipalcomponentanalysis(PCA)andtherecentlyestablishedrobustprincipalcomponentanalysis(RPCA)[7],matrixcompletion[8],andrecovery[9]methodsaresubstan-tiallybasedonthehypothesisthatdatalieonornearasinglelow-ranksubspace.Nonetheless,agivendatasetoftencontainssomedifferenttypesofstructurethatitishardtobewellcharacterizedbyasinglesubspace.Thedeficiencyoftheabovehypothesisnaturallyleadstoamorereasonablemodelthatdataisapproximatelydrawnfromamixtureofseveralsubspaces.ThismodelpresentsamorechallengingproblemofsubspaceManuscriptreceivedSeptember5,2012;revisedApril14,2013andAugust30,2013;acceptedOctober3,2013.DateofpublicationNovember1,2013;dateofcurrentversionJuly15,2014.ThisworkwassupportedinpartbytheNationalScienceFundforDistinguishedYoungScholarsunderGrant61125305,Grant61233011,andGrant61373063,andinpartbytheKeyProjectofChineseMinistryofEducationunderGrant313030.ThispaperwasrecommendedbyAssociateEditorL.Wang.TheauthorsarewiththeDepartmentofComputerScience,NanjingUniversityofScienceandTechnology,Nanjing210094,China(e-mail:[e-mail];[e-mail]).Colorversionsofoneormoreofthefiguresinthispaperareavailableonlineatfields,suchascomputervision,imageprocessing,machinelearning,andsystemidentification[10].Generally,theexistingsubspacesegmentationalgorithmcanberoughlydividedintothreemainfamilies:algebraic,statistical,andspectralclustering-basedmethods.Generalizedprincipalcomponentanalysis(GPCA)[11]isatypicallyalgebraicmethodforclusteringdatalyingonlinearsubspaces(notnecessarilyindependent).Thismethoddescribesasubspacewithapolynomialwhosederivativeatapointgivesavectornormaltothesubspace.Thesegmentationturnsintoanotherproblem:howtofitthedatawithpolynomi-als?Asaresultofthedifficultyofestimatingthepolynomialsfromrealdata,GPCAissensitivetonoisesandalsotimeconsuming.Abranchofalgebraicmethodsarefactorization-basedmethods[12],[13]whichobtainthesegmentationofthedatafromafactorizationofthedatamatrix.Inordertoachieverobustness,thesemethodsoftenmodifytheobjectivebyaddingextraregularizationterms,whichusuallyleadstononconvexproblem.Instatisticallearning,subspacesegmen-tationisaddressedwithprobabilisticframework,bymodelingmixeddataasasetofindependentsamplesdrawnfromamixtureofprobabilisticdistributions,suchasPPCA[14]andRANSAC[15].Unfortunately,thesemethodsarevulnerabletonoises,andtherefinementforrobustnessoftenleadstodifficultoptimizationproblem,whichisabottleneckoftheseproblems.Spectralclusteringalgorithmsusuallyconstructanaffinitymatrixfromthegivendata,andthengetthefinalresultbyusingsometraditionaltechniques,suchasK-meansalgorithm.Themainchallengefacedbyspectralclusteringmethodsishowtolearnagoodaffinitymatrix.Varioustechniqueshavebeendevelopedtolearnaneffectiveaffinitymatrix,includingSSC[16],SCC[17],andSR[18].Allthosemethodsarechallengedbytheerrorsexistinginthegivendata.Recently,therankminimizationhasgrabbedalotofatten-tion,andithasbeensuccessfullyusedinimagedenoising[19],motionestimation[20],matrixcompletion[8],[21]andrecov-ery[9],etc.Basedonthehypothesisthattheobserveddataisdrawnfromseveralindependentlow-ranksubspaces,Liu[22]proposedanewmethodforsubspacesegmentation,namely,low-rankrepresentation(LRR),whichaimstodecomposethedatamatrixasthesumofaclean,self-expressive,low-rankdictiona