{"data":{"id":"10.48550/arxiv.math/0410542","type":"dois","attributes":{"doi":"10.48550/arxiv.math/0410542","prefix":"10.48550","suffix":"arxiv.math/0410542","identifiers":[{"identifier":"math/0410542","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"math/0410542"}],"creators":[{"name":"Candes, Emmanuel","nameType":"Personal","givenName":"Emmanuel","familyName":"Candes","affiliation":[],"nameIdentifiers":[]},{"name":"Tao, Terence","nameType":"Personal","givenName":"Terence","familyName":"Tao","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Near Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?"}],"publisher":"arXiv","container":{},"publicationYear":2004,"subjects":[{"lang":"en","subject":"Classical Analysis and ODEs (math.CA)","subjectScheme":"arXiv"},{"lang":"en","subject":"Probability (math.PR)","subjectScheme":"arXiv"},{"subject":"FOS: Mathematics","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Mathematics","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"lang":"en","subject":"47B06; 42A10; 41A45; 65A99","subjectScheme":"MSC"}],"contributors":[],"dates":[{"date":"2004-10-25T23:51:59Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2009-12-01T04:35:12Z","dateType":"Updated","dateInformation":"v1"},{"date":"2005-04-03T21:42:37Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2009-12-01T04:35:12Z","dateType":"Updated","dateInformation":"v2"},{"date":"2006-04-04T23:25:47Z","dateType":"Submitted","dateInformation":"v3"},{"date":"2009-12-01T04:35:12Z","dateType":"Updated","dateInformation":"v3"},{"date":"2004-10","dateType":"Available","dateInformation":"v1"},{"date":"2004","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"3","rightsList":[{"rights":"Assumed arXiv.org perpetual, non-exclusive license to distribute this article for submissions made before January 2004","rightsUri":"http://arxiv.org/licenses/assumed-1991-2003/"}],"descriptions":[{"description":"Suppose we are given a vector $f$ in $\\R^N$. How many linear measurements do we need to make about $f$ to be able to recover $f$ to within precision $ε$ in the Euclidean ($\\ell_2$) metric? Or more exactly, suppose we are interested in a class ${\\cal F}$ of such objects--discrete digital signals, images, etc; how many linear measurements do we need to recover objects from this class to within accuracy $ε$? This paper shows that if the objects of interest are sparse or compressible in the sense that the reordered entries of a signal $f \\in {\\cal F}$ decay like a power-law (or if the coefficient sequence of $f$ in a fixed basis decays like a power-law), then it is possible to reconstruct $f$ to within very high accuracy from a small number of random measurements.","descriptionType":"Abstract"},{"description":"39 pages; no figures; to appear. Bernoulli ensemble proof has been corrected; other expository and bibliographical changes made, incorporating referee's suggestions","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi5NQVRILzA0MTA1NDI8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij5tYXRoLzA0MTA1NDI8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+Q2FuZGVzLCBFbW1hbnVlbDwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+RW1tYW51ZWw8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+Q2FuZGVzPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPlRhbywgVGVyZW5jZTwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+VGVyZW5jZTwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5UYW88L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgPC9jcmVhdG9ycz4KICA8dGl0bGVzPgogICAgPHRpdGxlPk5lYXIgT3B0aW1hbCBTaWduYWwgUmVjb3ZlcnkgRnJvbSBSYW5kb20gUHJvamVjdGlvbnM6IFVuaXZlcnNhbCBFbmNvZGluZyBTdHJhdGVnaWVzPzwvdGl0bGU+CiAgPC90aXRsZXM+CiAgPHB1Ymxpc2hlcj5hclhpdjwvcHVibGlzaGVyPgogIDxwdWJsaWNhdGlvblllYXI+MjAwNDwvcHVibGljYXRpb25ZZWFyPgogIDxzdWJqZWN0cz4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPkNsYXNzaWNhbCBBbmFseXNpcyBhbmQgT0RFcyAobWF0aC5DQSk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5Qcm9iYWJpbGl0eSAobWF0aC5QUik8L3N1YmplY3Q+CiAgICA8c3ViamVjdCBzdWJqZWN0U2NoZW1lPSJGaWVsZHMgb2YgU2NpZW5jZSBhbmQgVGVjaG5vbG9neSAoRk9TKSI+Rk9TOiBNYXRoZW1hdGljczwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iTVNDIj40N0IwNjsgNDJBMTA7IDQxQTQ1OyA2NUE5OTwvc3ViamVjdD4KICA8L3N1YmplY3RzPgogIDxkYXRlcz4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMDQtMTAtMjVUMjM6NTE6NTlaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMDktMTItMDFUMDQ6MzU6MTJaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MiI+MjAwNS0wNC0wM1QyMTo0MjozN1o8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MiI+MjAwOS0xMi0wMVQwNDozNToxMlo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYzIj4yMDA2LTA0LTA0VDIzOjI1OjQ3WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYzIj4yMDA5LTEyLTAxVDA0OjM1OjEyWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMDQtMTA8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlByZXByaW50Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHZlcnNpb24+MzwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vYXJ4aXYub3JnL2xpY2Vuc2VzL2Fzc3VtZWQtMTk5MS0yMDAzLyI+QXNzdW1lZCBhclhpdi5vcmcgcGVycGV0dWFsLCBub24tZXhjbHVzaXZlIGxpY2Vuc2UgdG8gZGlzdHJpYnV0ZSB0aGlzIGFydGljbGUgZm9yIHN1Ym1pc3Npb25zIG1hZGUgYmVmb3JlIEphbnVhcnkgMjAwNDwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPlN1cHBvc2Ugd2UgYXJlIGdpdmVuIGEgdmVjdG9yICRmJCBpbiAkXFJeTiQuIEhvdyBtYW55IGxpbmVhciBtZWFzdXJlbWVudHMgZG8gd2UgbmVlZCB0byBtYWtlIGFib3V0ICRmJCB0byBiZSBhYmxlIHRvIHJlY292ZXIgJGYkIHRvIHdpdGhpbiBwcmVjaXNpb24gJM61JCBpbiB0aGUgRXVjbGlkZWFuICgkXGVsbF8yJCkgbWV0cmljPyBPciBtb3JlIGV4YWN0bHksIHN1cHBvc2Ugd2UgYXJlIGludGVyZXN0ZWQgaW4gYSBjbGFzcyAke1xjYWwgRn0kIG9mIHN1Y2ggb2JqZWN0cy0tZGlzY3JldGUgZGlnaXRhbCBzaWduYWxzLCBpbWFnZXMsIGV0YzsgaG93IG1hbnkgbGluZWFyIG1lYXN1cmVtZW50cyBkbyB3ZSBuZWVkIHRvIHJlY292ZXIgb2JqZWN0cyBmcm9tIHRoaXMgY2xhc3MgdG8gd2l0aGluIGFjY3VyYWN5ICTOtSQ/IFRoaXMgcGFwZXIgc2hvd3MgdGhhdCBpZiB0aGUgb2JqZWN0cyBvZiBpbnRlcmVzdCBhcmUgc3BhcnNlIG9yIGNvbXByZXNzaWJsZSBpbiB0aGUgc2Vuc2UgdGhhdCB0aGUgcmVvcmRlcmVkIGVudHJpZXMgb2YgYSBzaWduYWwgJGYgXGluIHtcY2FsIEZ9JCBkZWNheSBsaWtlIGEgcG93ZXItbGF3IChvciBpZiB0aGUgY29lZmZpY2llbnQgc2VxdWVuY2Ugb2YgJGYkIGluIGEgZml4ZWQgYmFzaXMgZGVjYXlzIGxpa2UgYSBwb3dlci1sYXcpLCB0aGVuIGl0IGlzIHBvc3NpYmxlIHRvIHJlY29uc3RydWN0ICRmJCB0byB3aXRoaW4gdmVyeSBoaWdoIGFjY3VyYWN5IGZyb20gYSBzbWFsbCBudW1iZXIgb2YgcmFuZG9tIG1lYXN1cmVtZW50cy48L2Rlc2NyaXB0aW9uPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iT3RoZXIiPjM5IHBhZ2VzOyBubyBmaWd1cmVzOyB0byBhcHBlYXIuIEJlcm5vdWxsaSBlbnNlbWJsZSBwcm9vZiBoYXMgYmVlbiBjb3JyZWN0ZWQ7IG90aGVyIGV4cG9zaXRvcnkgYW5kIGJpYmxpb2dyYXBoaWNhbCBjaGFuZ2VzIG1hZGUsIGluY29ycG9yYXRpbmcgcmVmZXJlZSdzIHN1Z2dlc3Rpb25zPC9kZXNjcmlwdGlvbj4KICA8L2Rlc2NyaXB0aW9ucz4KPC9yZXNvdXJjZT4=","url":"https://arxiv.org/abs/math/0410542","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-18T06:34:20.000Z","registered":"2022-03-18T06:34:21.000Z","published":"2004","updated":"2022-03-18T06:34:21.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.math/0410542","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}