Convex Piecewise-Linear Fitting

ConvexPiecewise-LinearFittingAlessandroMagnaniStephenP.BoydyElectricalEngineeringDepartmentStanfordUniversityStanfordCA94305April13,2006AbstractWeconsidertheproblemofttingaconvexpiecewise-linearfunction,withsomespeciedform,togivenmulti-dimensionaldata.Exceptforafewspecialcases,thisproblemishardtosolveexactly,sowefocusonheuristicmethodsthatndlocallyoptimalts.Themethodwedescribe,whichisavariationontheK-meansalgorithmforclustering,seemstoworkwellinpractice,atleastondatathatcanbetwellbyaconvexfunction.Wefocusonthesimplestfunctionform,amaximumofaxednumberofanefunctions,andthenshowhowthemethodsextendtoamoregeneralform.[e-mail]@stanford.edu11Convexpiecewise-linearttingproblemWeconsidertheproblemofttingsomegivendata(u1;y1);:::;(um;ym)2RnRwithaconvexpiecewise-linearfunctionf:Rn!RfromsomesetFofcandidatefunctions.Withaleast-squaresttingcriterion,weobtaintheproblemminimizeJ(f)=Pmi=1(f(ui)yi)2subjecttof2F;(1)withvariablef.Wereferto(J(f)=m)1=2astheRMS(root-mean-square)tofthefunctionftothedata.Theconvexpiecewise-linearttingproblem(1)istondthefunctionf,fromthegivenfamilyFofconvexpiecewise-linearfunctions,thatgivesthebest(smallest)RMSttothegivendata.Ourmaininterestisinthecasewhenn(thedimensionofthedata)isrelativelysmall,saynotmorethan5orso,whilem(thenumberofdatapoints)canberelativelylarge,e.g.,104ormore.Themethodswedescribe,however,workforanyvaluesofnandm.Severalspecialcasesoftheconvexpiecewise-linearttingproblem(1)canbesolvedexactly.WhenFconsistsoftheanefunctions,i.e.,fhastheformf(x)=aTx+b,theproblem(1)reducestoanordinarylinearleast-squaresprobleminthefunctionparametersa2Rnandb2Randsoisreadilysolved.Asalesstrivialexample,considerthecasewhenFconsistsofallpiecewise-linearfunctionsfromRnintoR,withnootherconstraintontheformoff.Thisisthenonparametricconvexpiecewise-linearttingproblem.Thentheproblem(1)canbesolved,exactly,viaaquadraticprogram(QP);see[BV04,x6.5.5].Thisnonparametricapproach,however,hastwopotentialpracticaldisadvantages.First,theQPthatmustbesolvedisverylarge(containingmorethanmnvariables),limitingthemethodtomodestvaluesofm(say,athousand).Thesecondpotentialdisadvantageisthatthepiecewise-linearfunctiontobtainedcanbeverycomplex,withmanyterms(uptom).Ofcourse,notalldatacanbetwell(i.e.,withsmallRMSt)withaconvexpiecewise-linearfunction.Forexample,ifthedataaresamplesfromafunctionthathasstrongnegative(concave)curvature,thennoconvexfunctioncantitwell.Moreover,thebestt(whichwillbepoor)willbeobtainedwithananefunction.Wecanalsohavetheoppositesituation:itcanoccurthatthedatacanbeperfectlytbyananefunction,i.e.,wecanhaveJ=0.Inthiscasewesaythatthedataisinterpolatedbytheconvexpiecewise-linearfunctionf.1.1Max-anefunctionsInthispaperweconsidertheparametricttingproblem,inwhichthecandidatefunctionsareparametrizedbyanite-dimensionalvectorofcoecients2Rp.OneverysimpleformisgivenbyFkma,thesetoffunctionsonRnwiththeformf(x)=maxfaT1x+b1;:::;aTkx+bkg;(2)2i.e.,amaximumofkanefunctions.Werefertoafunctionofthisformas`max-ane',withkterms.ThesetFkmaisparametrizedbythecoecientvector=(a1;:::;ak;b1;:::;bk)2Rk(n+1):Infact,anyconvexpiecewise-linearfunctiononRncanbeexpressedasamax-anefunction,forsomek,sothisformisinasenseuniversal.Ourinterest,however,isinthecasewhenthenumberoftermskisrelativelysmall,saynomorethan10,orafew10s.Inthiscasethemax-anerepresentation(2)iscompact,inthesensethatthenumberofparametersneededtodescribef(i.e.,p)ismuchsmallerthanthenumberofparametersintheoriginaldataset(i.e.,m(n+1)).Themethodswedescribe,however,donotrequirektobesmall.WhenF=Fkma,thettingproblem(1)reducestothenonlinearleast-squaresproblemminimizeJ()=mXi=1maxj=1;:::;k(aTjui+bj)yi2;(3)withvariablesa1;:::;ak2Rn,b1;:::;bk2R.ThefunctionJisapiecewise-quadraticfunctionof.Indeed,foreachi,f(ui)yiispiecewise-linear,andJisthesumofsquaresofthesefunctions,soJisconvexquadraticonthe(polyhedral)regionsonwhichf(ui)isane.ButJisnotgloballyconvex,sothettingproblem(3)isnotconvex.1.2AmoregeneralparametrizationWewillalsoconsideramoregeneralparametrizedformforconvexpiecewise-linearfunctions,f(x)=((x;));(4)where:Rq!Risa(xed)convexpiecewise-linearfunction,and:RnRp!Rqisa(xed)bi-anefunction.(Thismeansthatforeachx,(x;)isananefunctionof,andforeach,(x;)isananefunctionofx.)Thesimplemax-aneparametrization(2)hasthisform,withq=k,(z1;:::;zk)=maxfz1;:::;zkg,andi(x;)=aTix+bi.Asanexample,considerthesetoffunctionsFthataresumsofkterms,eachofwhichisthemaximumoftwoanefunctions,f(x)=kXi=1maxfaTix+bi;cTix+dig;(5)parametrizedbya1;:::;ak;c1;:::;ck2Rnandb1;:::;bk;d1;:::;dk2R.Thisfamilycorrespondstothegeneralform(4)with(z1;:::;zk;w1;:::;wk)=kXi=1maxfzi;wig;and(x;)=(aT1x+b1;:::;aTkx+bk;cT1x+d1;:::;cTkx+dk):3Ofcoursewecanexpandanyfunctionwiththemoregeneralform(4)intoitsmax-anerepresentation.Buttheresultingmax-anerepresentationcanbeverymuchlargerthantheoriginalgeneralformrepresentation.Forexample,thefunctionform(5)requiresp=2k(n+1)parameters.Ifthesamefunctioniswrittenoutasamax-anefunction,itrequires2kterms,andtherefore2k(n+1)parameters.Theho