资源描述：
《error correction via linear programming》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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
