WRIGHTET
AL.:ROBUSTFACERECOGNITIONVIASPARSEREPRESENTATION213
Astheentriesofthevectorx0encodetheidentityofthetestsampley,itistemptingtoattempttoobtainitbysolvingthelinearsystemofequationsy¼Axx.Notice,though,thatusingtheentiretrainingsettosolveforxrepresentsasignificantdeparturefromonesampleoroneclassatatimemethodssuchasNNandNS.Wewilllaterarguethatonecanobtainamorediscriminativeclassifierfromsuchaglobalrepresentation.Wewilldemonstrateitssuperiorityovertheselocalmethods(NNorNS)bothforidentifyingobjectsrepresentedinthetrainingsetandforrejectingoutlyingsamplesthatdonotarisefromanyoftheclassespresentinthetrainingset.Theseadvantagescancomewithoutanincreaseintheorderofgrowthofthecomputation:Aswewillsee,thecomplexityremainslinearinthesizeoftrainingset.
Obviously,ifm>n,thesystemofequationsy¼Axxisoverdetermined,andthecorrectx0canusuallybefoundasitsuniquesolution.WewillseeinSection3,however,thatinrobustfacerecognition,thesystemy¼Axxistypicallyunderdetermined,andso,itssolutionisnotunique.6Conventionally,thisdifficultyisresolvedbychoosingtheminimum‘2-normsolution:
ð‘2Þ:
^2¼argminkxk2x
subjectto
Axx¼y:
ð4Þ
Fig.2.Geometryofsparserepresentationvia‘1-minimization.The
‘1-minimizationdetermineswhichfacet(ofthelowestdimension)ofthepolytopeAðP Þ,thepointy=kyk1liesin.Thetestsamplevectoryisrepresentedasalinearcombinationofjusttheverticesofthatfacet,withcoefficientsx0.
thatifthesolutionx0soughtissparseenough,thesolutionofthe‘0-minimizationproblem(5)isequaltothesolutiontothefollowing‘1-minimizationproblem:
ð‘1Þ:
^1¼argminkxk1x
subjecttoAxx¼y:
ð6Þ
Whilethisoptimizationproblemcanbeeasilysolved(via
^2isnotespeciallythepseudoinverseofA),thesolutionx
informativeforrecognizingthetestsampley.AsshowninExample1,x^2isgenerallydense,withlargenonzeroentriescorrespondingtotrainingsamplesfrommanydifferentclasses.Toresolvethisdifficulty,weinsteadexploitthefollowingsimpleobservation:Avalidtestsampleycanbesufficientlyrepresentedusingonlythetrainingsamplesfromthesameclass.Thisrepresentationisnaturallysparseifthenumberofobjectclasseskisreasonablylarge.Forinstance,ifk¼20,only5percentoftheentriesofthedesiredx0shouldbenonzero.Themoresparsetherecoveredx0is,theeasierwillitbetoaccuratelydeterminetheidentityofthetestsampley.7
Thismotivatesustoseekthesparsestsolutiontoy¼Axx,solvingthefollowingoptimizationproblem:
ð‘0Þ:
^0¼argminkxk0x
subjectto
Axx¼y;
ð5Þ
Thisproblemcanbesolvedinpolynomialtimebystandard
linearprogrammingmethods[34].Evenmoreefficientmethodsareavailablewhenthesolutionisknowntobeverysparse.Forexample,homotopyalgorithmsrecoversolutionswithtnonzerosinOðt3þnÞtime,linearinthesizeofthetrainingset[35].
2.2.1GeometricInterpretation
Fig.2givesageometricinterpretation(essentiallydueto[36])ofwhyminimizingthe‘1-normcorrectlyrecoverssufficientlysparsesolutions.LetP denotethe‘1-ball(orcrosspolytope)ofradius :
:
ð7ÞP ¼fx:kxk1 g&IRn:InFig.2,theunit‘1-ballP1ismappedtothepolytope
:
xforP¼AðP1Þ&IRm,consistingofallythatsatisfyy¼Ax
1
somexwhose‘-normis 1.
ThegeometricrelationshipbetweenP andthepolytopeAðP Þisinvarianttoscaling.Thatis,ifwescaleP ,itsimageundermultiplicationbyAisalsoscaledbythesameamount.Geometrically,findingtheminimum‘1-norm
^1to(6)isequivalenttoexpandingthe‘1-ballP solutionx
untilthepolytopeAðP Þfirsttouchesy.Thevalueof at
^1k1.whichthisoccursisexactlykx
Now,supposethaty¼Axx0forsomesparsex0.Wewishtoknowwhensolving(6)correctlyrecoversx0.Thisquestioniseasilyresolvedfromthegeometryofthatin
^1isfoundbyexpandingbothP andAðP ÞFig.2:Sincex
^1mustuntilapointofAðP Þtouchesy,the‘1-minimizerx
^1ontheboundaryofP.generateapointAx
^1¼x0ifandonlyifthepointAðx0=kx0k1ÞliesonThus,x
theboundaryofthepolytopeP.FortheexampleshowninFig.2,itiseasytoseethatthe‘1-minimizationrecoversallx0withonlyonenonzeroentry.ThisequivalenceholdsbecausealloftheverticesofP1maptopointsontheboundaryofP.
Ingeneral,ifAmapsallt-dimensionalfacetsofP1tofacetsofP,thepolytopePisreferredtoas(centrally)t-neighborly[36].Fromtheabove,weseethatthe‘1-minimization(6)correctlyrecoversallx0with tþ1nonzerosifandonlyifPist-neighborly,inwhichcase,itis
wherekÁk0denotesthe‘0-norm,whichcountsthenumberofnonzeroentriesinavector.Infact,ifthecolumnsofAareingeneralposition,thenwhenevery¼Axxforsomexwithlessthanm=2nonzeros,xistheuniquesparsestsolution:^0¼x[33].However,theproblemoffindingthesparsestx
solutionofanunderdeterminedsystemoflinearequationsisNP-hardanddifficulteventoapproximate[13]:thatis,inthegeneralcase,noknownprocedureforfindingthesparsestsolutionissignificantlymoreefficientthanexhaustingallsubsetsoftheentriesforx.
2.2SparseSolutionvia‘1-Minimization
Recentdevelopmentintheemergingtheoryofsparserepresentationandcompressedsensing[9],[10],[11]reveals
6.Furthermore,evenintheoverdeterminedcase,suchalinearequationmaynotbeperfectlysatisfiedinthepresenceofdatanoise(seeSection2.2.2).
7.Thisintuitionholdsonlywhenthesizeofthedatabaseisfixed.Forexample,ifweareallowedtoappendadditionalirrelevantcolumnstoA,wecanmakethesolutionx0haveasmallerfractionofnonzeros,butthisdoesnotmakex0moreinformativeforrecognition.