214IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.31,NO.2,FEBRUARY
2009
Fig.3.Avalidtestimage.(a)Recognitionwith12Â10downsampledimagesasfeatures.Thetestimageybelongstosubject1.ThevaluesofthesparsecoefficientsrecoveredfromAlgorithm1areplottedontherighttogetherwiththetwotrainingexamplesthatcorrespondtothetwolargest
^Þby‘1-minimization.Thesparsecoefficients.(b)TheresidualsriðyÞofatestimageofsubject1withrespecttotheprojectedsparsecoefficients iðx
ratiobetweenthetwosmallestresidualsisabout1:8.6.
equivalenttothe‘0-minimization(5).8Thisconditionissurprisinglycommon:evenpolytopesPgivenbyrandommatrices(e.g.,uniform,Gaussian,andpartialFourier)arehighlyneighborly[15],allowingcorrectrecoverofsparsex0by‘1-minimization.
Unfortunately,thereisnoknownalgorithmforeffi-cientlyverifyingtheneighborlinessofagivenpolytopeP.Thebestknownalgorithmiscombinatorial,andtherefore,onlypracticalwhenthedimensionmismoderate[37].Whenmislarge,itisknownthatwithoverwhelmingprobability,theneighborlinessofarandomlychosenpolytopePislooselyboundedbetween
cÁm<t<bðmþ1Þ=3c;
ð8Þ
forsomesmallconstantc>0(see[9]and[36]).Looselyspeaking,aslongasthenumberofnonzeroentriesofx0isasmallfractionofthedimensionm,‘1-minimizationwillrecoverx0.
2.2.2DealingwithSmallDenseNoise
Sofar,wehaveassumedthat(3)holdsexactly.Sincerealdataarenoisy,itmaynotbepossibletoexpressthetestsampleexactlyasasparsesuperpositionofthetrainingsamples.Themodel(3)canbemodifiedtoexplicitlyaccountforsmallpossiblydensenoisebywriting
y¼Axx0þz;
ð9Þ
wherez2IRmisanoisetermwithboundedenergy
kzk2<".Thesparsesolutionx0canstillbeapproximatelyrecoveredbysolvingthefollowingstable‘1-minimizationproblem:ð‘1sÞ:
^1¼argminkxk1x
subjectto
kAxxÀyk2 ":
ð10Þ
Thisconvexoptimizationproblemcanbeefficientlysolvedviasecond-orderconeprogramming[34](seeSection4forouralgorithmofchoice).Thesolutionofð‘1sÞisguaranteedtoapproximatelyrecoverysparsesolutionsinensemblesofrandommatricesA[38]:Thereareconstants and suchthatwithoverwhelmingprobability,ifkx0k0<
^1satisfies mandkzk2 ",thenthecomputedx
^1Àx0k2 ":kx
ð11Þ
2.3ClassificationBasedonSparseRepresentation
Givenanewtestsampleyfromoneoftheclassesinthe
^1trainingset,wefirstcomputeitssparserepresentationx^1via(6)or(10).Ideally,thenonzeroentriesintheestimatex
willallbeassociatedwiththecolumnsofAfromasingleobjectclassi,andwecaneasilyassignthetestsampleytothatclass.However,noiseandmodelingerrormayleadtosmallnonzeroentriesassociatedwithmultipleobjectclasses(seeFig.3).Basedontheglobalsparserepresenta-tion,onecandesignmanypossibleclassifierstoresolvethis.Forinstance,wecansimplyassignytotheobjectclass
^1.However,suchheuristicswiththesinglelargestentryinx
donotharnessthesubspacestructureassociatedwithimagesinfacerecognition.Tobetterharnesssuchlinearstructure,weinsteadclassifyybasedonhowwellthecoefficientsassociatedwithalltrainingsamplesofeachobjectreproducey.
Foreachclassi,let i:IRn!IRnbethecharacteristicfunctionthatselectsthecoefficientsassociatedwiththeithclass.Forx2IRn, iðxÞhttp://www.77cn.com.cningonlythecoefficientsassociatedwiththeithclass,onecanapproximatethegiventestsampleyas^i¼A iðx^1Þ.Wethenclassifyybasedontheseapproxima-y
tionsbyassigningittotheobjectclassthatminimizesthe
^i:residualbetweenyandy:
minriðyÞ¼kyÀA iðx^1Þk2:ð12Þ
i
Algorithm1belowsummarizesthecompleterecognition
procedure.Ourimplementationminimizesthe‘1-normviaaprimal-dualalgorithmforlinearprogrammingbasedon[39]and[40].
Algorithm1.SparseRepresentation-basedClassification(SRC)
1:Input:amatrixoftrainingsamples
A¼½A1;A2;...;Ak 2IRmÂnforkclasses,atestsampley2IRm,(andanoptionalerrortolerance">0.)2:NormalizethecolumnsofAtohaveunit‘2-norm.3:Solvethe‘1-minimizationproblem:
^1¼argminxkxk1subjecttoAxx¼y:ð13Þx
(Oralternatively,solve
^1¼argminxkxk1subjecttokAxxÀyk2 ":Þx
^1Þk24:ComputetheresidualsriðyÞ¼kyÀA iðx
fori¼1;...;k.
5:Output:identityðyÞ¼argminiriðyÞ.
8.Thus,neighborlinessgivesanecessaryandsufficientconditionforsparserecovery.Therestrictedisometrypropertiesoftenusedinanalyzingtheperformanceof‘1-minimizationinrandommatrixensembles(e.g.,[15])givesufficient,butnotnecessary,conditions.