WRIGHTETAL.:ROBUSTFACERECOGNITIONVIASPARSEREPRESENTATION217
Fig.6.Examplesoffeatureextraction.(a)Originalfaceimage.(b)120Drepresentationsintermsoffourdifferentfeatures(fromlefttoright):Eigenfaces,Laplacianfaces,downsampled(12Â10pixel)image,andrandomprojection.Wewilldemonstratethatallthesefeaturescontainalmostthesameinformationabouttheidentityofthesubjectandgivesimilarlygoodrecognitionperformance.(c)Theeyeisapopularchoiceoffeaturefor
~¼Ry~.facerecognition.Inthiscase,thefeaturematrixRissimplyabinarymask.(a)Originaly.(b)120Dfeaturesyy.(c)Eyefeaturey
RA2IRdÂnofd-dimensionalfeatures;thetestimageyis
~.replacedbyitsfeaturesy
Forextantfacerecognitionmethods,empiricalstudieshaveshownthatincreasingthedimensiondofthefeaturespacegenerallyimprovestherecognitionrate,aslongasthedistributionoffeaturesRAidoesnotbecomedegenerate[42].Degeneracyisnotanissuefor‘1-minimization,sinceit
~beinorneartherangeofRAi—itmerelyrequiresthaty
T
doesnotdependonthecovarianceÆi¼ATiRRAibeingnonsingularasinclassicaldiscriminantanalysis.Thestableversionof‘1-minimization(10)or(17)isknowninstatisticalliteratureastheLasso[14].11Iteffectivelyregularizeshighlyunderdeterminedlinearregressionwhenthedesiredsolu-tionissparseandhasalsobeenprovenconsistentinsomenoisyoverdeterminedsettings[12].
Foroursparserepresentationapproachtorecognition,wewouldliketounderstandhowthechoiceofthefeatureextractionRaffectstheabilityofthe‘1-minimization(17)torecoverthecorrectsparsesolutionx0.Fromthegeometricinterpretationof‘1-minimizationgiveninSection2.2.1,theanswertothisdependsonwhethertheassociatednewpolytopeP¼RAðP1Þremainssufficientlyneighborly.ItiseasytoshowthattheneighborlinessofthepolytopeP¼RAðP1Þincreaseswithd[11],[15].InSection4,ourexperimentalresultswillverifytheabilityof‘1-minimiza-tion,inparticular,thestableversion(17),torecoversparserepresentationsforfacerecognitionusingavarietyoffeatures.Thissuggeststhatmostdata-dependentfeaturespopularinfacerecognition(e.g.,eigenfacesandLaplacian-faces)mayindeedgivehighlyneighborlypolytopesP.
Furtheranalysisofhigh-dimensionalpolytopegeometryhasrevealedasomewhatsurprisingphenomenon:ifthesolutionx0issparseenough,thenwithoverwhelmingprobability,itcanbecorrectlyrecoveredvia‘1-minimizationfromanysufficientlylargenumberdoflinearmeasurements~¼RAxyx0.Moreprecisely,ifx0hast(nnonzeros,thenwithoverwhelmingprobability
d!2tlogðn=dÞ
ð18Þ
randomlinearmeasurementsaresufficientfor‘1-minimiza-tion(17)torecoverthecorrectsparsesolutionx0[44].12Thissurprisingphenomenonhasbeendubbedthe“blessingofdimensionality”[15],[46].Randomfeaturescanbeviewedasaless-structuredcounterparttoclassicalfacefeaturessuchasEigenfacesorFisherfaces.Accordingly,wecallthelinearprojectiongeneratedbyaGaussianrandommatrixRandomfaces.13
Definition2(randomfaces).ConsideratransformmatrixR2IRdÂmwhoseentriesareindependentlysampledfromazero-meannormaldistribution,andeachrowisnormalizedtounitlength.TherowvectorsofRcanbeviewedasdrandomfacesinIRm.OnemajoradvantageofRandomfacesisthattheyareextremelyefficienttogenerate,asthetransformationRisindependentofthetrainingdataset.Thisadvantagecanbeimportantforafacerecognitionsystem,wherewemaynotbeabletoacquireacompletedatabaseofallsubjectsofinteresttoprecomputedata-dependenttransformationssuchasEigenfaces,orthesubjectsinthedatabasemaychangeovertime.Insuchcases,thereisnoneedforrecomputingtherandomtransformationR.
Aslongasthecorrectsparsesolutionx0canberecovered,Algorithm1willalwaysgivethesameclassifica-tionresult,regardlessofthefeatureactuallyused.Thus,whenthedimensionoffeaturedexceedstheabovebound(18),oneshouldexpectthattherecognitionperformanceofAlgorithm1withdifferentfeaturesquicklyconverges,andthechoiceofan“optimal”featuretransformationisnolongercritical:evenrandomprojectionsordownsampledimagesshouldperformaswellasanyothercarefullyengineeredfeatures.ThiswillbecorroboratedbytheexperimentalresultsinSection4.
3.2RobustnesstoOcclusionorCorruption
Inmanypracticalfacerecognitionscenarios,thetestimageycouldbepartiallycorruptedoroccluded.Inthiscase,theabovelinearmodel(3)shouldbemodifiedas
y¼y0þe0¼Ax0þe0;
ð19Þ
11.Classically,theLassosolutionisdefinedastheminimizerofkyÀAxxk22þ kxk1.Here, canbeviewedasinverseoftheLagrangemultiplierassociatedwithaconstraintkyÀAxxk22 ".Forevery ,thereisan"suchthatthetwoproblemshavethesamesolution.However,"canbeinterpretedasapixelnoiselevelandfixedacrossvariousinstancesoftheproblem,whereas cannot.OneshoulddistinguishtheLassooptimizationproblemfromtheLARSalgorithm,whichprovablysolvessomeinstancesofLassowithverysparseoptimizers[35].
12.Strictlyspeaking,thisthresholdholdswhenrandommeasurements
~¼Rxarecomputeddirectlyfromx0,i.e.,yx0.Nevertheless,ourexperiments
roughlyagreewiththeboundgivenby(18).Thecasewherex0isinsteadsparseinsomeovercompletebasisA,andweobservethatrandom
~¼RAxmeasurementsyx0hasalsobeenstudiedin[45].Whileconditionsfor
correctrecoveryhavebeengiven,theboundsarenotyetassharpas(18)above.
13.Randomprojectionhasbeenpreviouslystudiedasageneraldimensionality-reductionmethodfornumerousclusteringproblems[47],[48],[49],
aswellasforlearningnonlinearmanifolds[50],[51].