資源描述：
《error correction via linear programming》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、ErrorCorrectionviaLinearProgrammingEmmanuelCandesMarkRudelsonTerenceTaoAppliedandComputationalDepartmentofMathematicsDepartmentofMathematicsMathematics,Caltech,UniversityofMissouri,UniversityofCalifornia,Pasadena,CA91125,USAColumbia,MO65203,USALosAngeles,CA90095,USAemman
2、uel@acm.caltech.edurudelson@math.missouri.edutao@math.ucla.eduRomanVershyninDepartmentofMathematicsUniversityofCalifornia,Davis,CA9595616,USAvershynin@math.ucdavis.eduAbstractearcodes,sparsesolutionstounderdeterminedsystems,`1-minimization,linearprogramming,restrictedort
3、honormal-Supposewewishtotransmitavectorf∈Rnreliably.Aity,Gaussianrandommatrices.frequentlydiscussedapproachconsistsinencodingfwithanmbyncodingmatrixA.Assumenowthatafraction1IntroductionoftheentriesofAfarecorruptedinacompletelyarbitraryfashionbyanerrore.Wedonotknowwhichen
4、triesareaffectednordoweknowhowtheyareaffected.Isitpossi-1.1Theerrorcorrectionproblembletorecoverfexactlyfromthecorruptedm-dimensionalvectory0=Af+e?Thispaperconsidersthemodelproblemofrecoveringaninputvectorf∈RnfromcorruptedmeasurementsThispaperprovesthatundersuitablecondi
5、tionsonthey0=Af+e.Here,Aisanmbynmatrix(wewillas-codingmatrixA,theinputfistheuniquesolutiontothePsumethroughoutthepaperthatm>n),ande∈Rmis`1-minimizationproblem(kxk`1:=i
6、xi
7、)anunknownvectoroferrors.Wewillassumethatatmostminky0?Af?k`1rentriesarecorrupted,thusatmostrentrieso
8、fearenon-f?∈Rnzero,butapartfromthisrestrictionewillbearbitrary.Theprovidedthatthefractionofcorruptedentriesisnottooproblemweconsideriswhetheritispossibletorecoverflarge,i.e.doesnotexceedsomestrictlypositiveconstantexactlyfromthedatay.Andifso,how?ρ?(numericalvaluesforρ?ar
9、eactuallygiven).InotherInitsabstractform,ourproblemisofcourseequivalentwords,fcanberecoveredexactlybysolvingasimpletotheclassicalerrorcorrectingproblemwhicharisesincod-convexoptimizationproblem;infact,alinearprogram.ingtheoryaswemaythinkofAasalinearcode;alinearWereporton
10、numericalexperimentssuggestingthat`1-codeisagivencollectionofcodewordswhicharevectorsminimizationisamaz
