搜索
1TheSimplestSolutiontoanUnderdeterminedSystemofLinearEquationsDavidDonohoDepartmentofStatisticsStanfordUniversityHosseinKakavand,JamesMammenDepartmentofElectricalEngineeringStanfordUniversityEmail:{Donoho,hossein,jmammen}@stanford.eduAbstractConsiderad×nmatrixA,withdn.Theproblemofsolvingforxiny=Axisunderdetermined,andhasinfinitelymanysolutions(ifthereareany).Giveny,theminimumKolmogorovcomplexitysolution(MKCS)oftheinputxisdefinedtobeaninputz(outofmany)withminimumKolmogorov-complexitythatsatisfiesy=Az.Oneexpectsthatiftheactualinputissimpleenough,thenMKCSwillrecovertheinputexactly.Thispaperpresentsapreliminarystudyoftheexistenceandvalueofthecomplexityleveluptowhichsuchacomplexity-basedrecoveryispossible.Itisshownthatforthesetofalld×nbinarymatrices(withentries0or1anddn),MKCSexactlyrecoverstheinputforanoverwhelmingfractionofthematricesprovidedtheKolmogorovcomplexityoftheinputisO(d).Aweakconversethatisloosebyalognfactorisalsoestablishedforthiscase.Finally,weinvestigatethedifficultyoffindingamatrixthathasthepropertyofrecoveringinputswithcomplexityofO(d)usingMKCS.IndexTermsAlgorithmicinformationtheory,complexity-basedrecovery,Kolmogorovcomplexity,underdeterminedsystemoflinearequations.I.INTRODUCTIONManyimportanttechnologicalproblemsrequiresolutionstounderdeterminedsystemsoflinearequations,i.e.,systemsoflinearequationswithfewerequationsthanunknowns.Examplesariseinlinearfiltering,arraysignalprocessing,andinverseproblems.Foranunderdeterminedsystemoflinearequations,ifthereisanysolution,2thereareinfinitelymanysolutions.Inmanyapplications,the“simplest”solutionismostacceptable.SuchasolutionisinspiredbytheminimalistprincipleofOccam’sRazor.Forexample,iftheparametersofamodelarebeingestimatedthenamongallmodelsthatexplainthedataequallywell,theonewiththeminimumnumberofparametersismostdesirable.Themodelwiththeminimumnumberofparametersis,infact,thesparsestsolution.Thusinthisexample,oneislookingforthesparsestsolutionandsimplicitycorrespondstosparseness.Anunderdeterminedsystemoflinearequations,y=Ax,hasinfinitelymanysolutions(ifthereareany)andtheyformanaffinespace.TheprincipleofOccam’sRazorinspireschoosingthesimplest,i.e.,theleastcomplexsolutioninthisaffinespace.Inordertomeasurecomplexity,weuseKolmogorovcomplexity,whichisafundamentalnotioninalgorithmicinformationtheory.Clearly,iftheKolmogorovsimplestsolutionisuniqueandxissimpleenoughthenitcanberecoveredfromy=Axbychoosingthesimplestsolution.Thequestionthenis:howsimpleshouldtheinputbesothatitcanberecoveredasthesimplestsolution?Clearlyiftheinputissufficientlycomplex,itcannotberecoveredusingthisapproachofchoosingthesimplestsolution.Thissuggeststheexistenceofacomplexitythresholdbelowwhichallinputscanberecoveredandabovewhichrecoveryisnotpossibleforallinputs.Inthispaper,weconductapreliminarystudyanddiscovertheexistenceofacomplexitythresholdforthefamilyofd×nbinarymatrices.Therestofthepaperisorganizedasfollows.InSectionII,wepresentsomepreliminariesonKolmogorovcomplexityandmakeprecisethenotionofcomplexitybasedrecoveryandcomplexitythreshold.InSectionIII,westudythefamilyofd×nbinarymatrices.WefirstshowthatanyinputsequencewithcomplexityofO(d)canberecoveredforallbutavanishingfractionofthesebinarymatrices.ThusmostbinarymatricesallowcomplexitybasedrecoveryforinputsuptocomplexityofO(d).Wealsoderiveaweakconversetothisresultthatisoffbyalogarithmicfactor.Thisestablishesthecomplexitythresholdforthefamilyofd×nbinarymatricestoberoughlyoforderd.InSectionIV,weexplorethepossibilityofprovidingaconcreteexampleofamatrixthatallowscomplexitybasedrecoveryforinputswithcomplexityofO(d)(sinceweknowthatmanysuchmatricesexist).OurresultssuggestthatifamatrixcanbeeasilydescribedthencomplexitybasedrecoveryisnotpossibleuptoinputcomplexityofO(d).WespecificallyshowsuchanexamplebyconstructingafamilyofbinarymatricesusingWalshfunctions.II.PRELIMINARIESWefirstintroducethebasicnotionsinalgorithmicinformationtheoryusedthroughoutthepaper,includingTuringmachines,universalTuringmachines,Kolmogorovcomplexity,andconditionalKolmogorovcomplexity.Forformaldefinitionsandcomprehensivedescriptionssee[1],[4],[5].Usingthesebasicnotions,wethendefinetheminimumKolmogorovcomplexityestimatorinoursetting,whichissimilarinspirittotheonein[2].ATuringmachineisafinitecomputingdeviceequippedwithanunboundedmemory.Thereareseveral3equivalentdefinitionsandweusethefollowingdescriptionsuitedtoourpurpose.ThememoryoftheTuringMachineisgivenintheformoftwotapes–aninputtapeandanoutputtape.Eachtapeisdividedintoaninfinitenumberofcellsinbothdirections.Oneachtape,asymbolfromafinitealphabetΣcanbewritten.ΣcontainsaspecialsymbolBthatdenotesanemptycell.LetΣ0=Σ\B.Toaccesstheinformationonthetapes,eachtapeissuppliedbyaread-writehead.Timeisdiscreteandateverystep,eachheadsitsonacellofitscorrespondingtape.Theheadsareconnectedtoacontrolunitwithafinitenumberofstatesincludingadistinguishedstartingstate“START”andahaltingstate“STOP”.Inthebeginning,theoutputtapeisempty,i.e.,eachcellcontainsB.WhereasontheinputtapeafinitenumberofcontiguouscellscontainelementsinΣ0andtherestareB.Thisfinitesequenceiscalledtheprogr