Stability and instance optimality for Gaussian

《Stability and instance optimality for Gaussian》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、StabilityandinstanceoptimalityforGaussianmeasurementsincompressedsensingP.WojtaszczykyInstitutofAppliedMathematicsUniversityofWarsawul.Banacha2;02-097WarszawaPolandFebruary14,2008AbstractIncompressedsensingweseektogaininformationaboutvectorx2NRfromd<

2、velinearmeasurements.Candes,Donoho,Taoet.al.(seee.g.[2,4,8])proposedtoseekgoodapproximationtoxvia`1minimisation.InthispaperweshowthatinthecaseofGaussianmeasurementsitrecoversthesignalwellfrominacuratemeasurements,thusimprovingresultfrom[4].Wealsoshowthatwithbigp

3、robabilityitgivesinformationcomparablewithbestktermapproximationineuclideannorm,kd=lnN.Thisprovidestherstnumericallyfriendlyalgorithmtodoso,see[7].1IntroductionCompressedsensingisanewschemewhichshowsthatsomesignalscanbere-constructedfromfewermeasurementsthatpr

4、eviouslywereconsiderednecessary.Themathematicalformulationisthefollowing.Oursignalisavectorx2RN.WehaveaNdmatrixcalledmeasurementmatrixandourmeasurementsarerepresentedbyy=(x)2Rd.Wealsoneedadecoder
(whichmaybenon-linear)whichproduces
(y)2RNwhichshouldbeanapprox

5、imationtox.Themainpointincompressedsensingasexpressedinrecentpapersisthatitisactuallypossibletorecovertheessentialinformationaboutxfromrelativelyfewnon-adaptivemeasurementsd<

6、thorwouldliketoexpresshisgratitudetoPiotrMankiewiczforansweringquestionsaboutconvexgeometryandtoAlbertCohen,WolfgangDahmenandRonDeVoreforteachinghimcompressedsensing.ThanksarealsoduetoRachelWardforinterestingdiscussionaboutstabilityresults.Thisresearchwasmadepos

7、siblebyECMarieCurieToKprogramSPADE-2atIMPAN1recentyearsinunderstandingtheperformanceofvariousmeasurementmatricesanddecoders
.Generallywehavealsoanintegerkdwhichmeasurestheamountofinformationwewishtorecover.Thestandardinitialrequirementisthatforeveryk{sparsevec

8、tor(i.e.x2k)wehave
((x))=x.Thisclearlyforcesjktobeonetoone.Butfoe
tobenumericallyfriendlywemusthavethecorrespondingsystemsofequationswellconditioned.Thisleadstoth