{"id":1799,"date":"2017-10-12T18:12:31","date_gmt":"2017-10-12T23:12:31","guid":{"rendered":"http:\/\/blogs.ams.org\/beyondreviews\/?p=1799"},"modified":"2018-03-14T08:54:31","modified_gmt":"2018-03-14T13:54:31","slug":"emmanuel-candes-macarthur-fellow","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/beyondreviews\/2017\/10\/12\/emmanuel-candes-macarthur-fellow\/","title":{"rendered":"Emmanuel Cand\u00e8s – MacArthur Fellow"},"content":{"rendered":"
\"Photo

Emmanuel Cand\u00e8s (Source Wikimedia)<\/p><\/div>\n

Emmanuel Cand\u00e8s<\/a> has won a prestigious MacArthur Fellowship.\u00a0 The official announcement is here<\/a>.\u00a0 The LA Times has a nice write-up<\/a>.\u00a0 \u00a0Both the Los Angeles Times and the MacArthur announcement highlight Cand\u00e8s’s work on compressed sensing.\u00a0 Terry Tao<\/a> has a spot-on reaction to this work, quoted in the LA Times, typical of most mathematicians when you first hear about the method:\u00a0 you can’t be getting be getting something for nothing.\u00a0 This can’t work.<\/em>\u00a0 But it does!\u00a0 Tao finally came around to believe it, as has the rest of the world.\u00a0\u00a0<\/p>\n

Cand\u00e8s is a collaborative researcher.\u00a0 The work on compressed sensing came out of conversations he was having initially with researchers in imaging science (MRIs).\u00a0 He tested out his ideas in conversations with Tao (while picking up their children at daycare, according to the legend).\u00a0 In MathSciNet, you can see that Cand\u00e8s has 48 coauthors<\/a>, representing a wide variety of people: statisticians, analysts,\u00a0 younger collaborators, older collaborators.<\/p>\n

One of his key publications on compressed sensing is his paper<\/a> with\u00a0Justin Romberg<\/a> and Terry Tao<\/a> in\u00a0Communications on Pure and Applied Mathematics,<\/em><\/a>\u00a0 Stable signal recovery from incomplete and inaccurate measurements.\u00a0 For your reading enjoyment, our review of it is reproduced below.\u00a0 The complete article is here<\/a>.<\/p>\n

Congratulations, Emmanuel Cand\u00e8s!<\/p>\n

\n

MR2230846<\/strong><\/a>
\nCand\u00e8s, Emmanuel J.<\/a>(1-CAIT-ACM)<\/a><\/span>;\u00a0Romberg, Justin K.<\/a>(1-CAIT-ACM)<\/a><\/span>;\u00a0Tao, Terence<\/a>(1-UCLA)<\/a><\/span>
\nStable signal recovery from incomplete and inaccurate measurements.<\/span>
\nComm. Pure Appl. Math.<\/em><\/a>\u00a059\u00a0<\/a>(2006),\u00a0<\/a>no. 8,<\/a>\u00a01207\u20131223.
\n94A12<\/a><\/p>\n

The authors consider the problem of recovering an unknown sparse signal\u00a0$x_0(t)inBbb{R}^m$<\/span>\u00a0from\u00a0$nll m$<\/span>\u00a0linear measurements which are corrupted by noise, building on related results in [E. J. Cand\u00e8s and J. K. Romberg, Found. Comput. Math.\u00a06<\/span>\u00a0(2006), no. 2, 227\u2013254;\u00a0MR2228740<\/a>; E. J. Cand\u00e8s, J. K. Romberg and T. C. Tao, IEEE Trans. Inform. Theory\u00a052<\/span>\u00a0(2006), no. 2, 489\u2013509;\u00a0MR2236170<\/a>; E. J. Cand\u00e8s and T. C. Tao, IEEE Trans. Inform. Theory\u00a051<\/span>\u00a0(2005), no. 12, 4203\u20134215;\u00a0MR2243152<\/a>; “Near optimal signal recovery from random projections: universal encoding strategies?”, preprint,\u00a0arxiv.org\/abs\/math.CA\/0410542<\/a>, IEEE Trans. Inform. Theory, submitted; D. L. Donoho, Comm. Pure Appl. Math.\u00a059<\/span>\u00a0(2006), no. 6, 797\u2013829;\u00a0MR2217606<\/a>]. Here\u00a0$x_0(t)$<\/span>is said to be sparse if its support\u00a0$T_{0}=lbrace tcolon x_0(t)neq0rbrace$<\/span>\u00a0has small cardinality. The measurements are assumed to be of the form\u00a0$y=Ax_0+ e$<\/span>, where\u00a0$A$<\/span>\u00a0is the\u00a0$ntimes m$<\/span>\u00a0measurement matrix and the error term\u00a0$e$<\/span>\u00a0satisfies\u00a0$Vert eVert_{l_{2}}leepsilon$<\/span>. Given this setup, consider the convex program\u00a0$$ minVert xVert_{l_{1}} {rm subject to};Vert Ax-y Vert_{l_{2}}leepsilon.;;;(textrm {P}_{2}) $$<\/span><\/p>\n

The authors define\u00a0$A_{T}$<\/span>,\u00a0$Tsubsetlbrace 1,ldots,mrbrace$<\/span>, to be the\u00a0$ntimesvert Tvert$<\/span>\u00a0submatrix obtained by extracting the columns of\u00a0$A$<\/span>\u00a0corresponding to the indices in\u00a0$T$<\/span>. Their results are stated in terms of the\u00a0$S$<\/span>-restricted isometry constant\u00a0$delta_S$<\/span>\u00a0of\u00a0$A$<\/span>\u00a0[E. J. Cand\u00e8s and T. C. Tao, op. cit., 2005], which is the smallest quantity such that\u00a0$$ (1-delta_{S})Vert cVert_{l_{2}}^{2}leVert A_{T}c Vert_{l_{2}}^{2}le(1+delta_{S})Vert cVert_{l_{2}}^2 $$<\/span>\u00a0for all subsets\u00a0$T$<\/span>\u00a0with\u00a0$vert Tvertle S$<\/span>\u00a0and coefficient sequences\u00a0$(c_{j})_{jin T}$<\/span>.<\/p>\n

Their main results are below. The first describes stable recovery of sparse signals, while the second yields stable recovery for approximately sparse signals by focusing on the\u00a0$S$<\/span>\u00a0largest components of the signal\u00a0$x_0$<\/span>.<\/p>\n

Theorem 1. Let\u00a0$S$<\/span>\u00a0be such that\u00a0$delta_{3S}+3delta_{4S}<2$<\/span>. Then for any signal\u00a0$x_{0}$<\/span>\u00a0supported on\u00a0$T_0$<\/span>\u00a0with\u00a0$vert T_0vertle S$<\/span>\u00a0and any perturbation\u00a0$e$<\/span>\u00a0with\u00a0$Vert eVert_{l_{2}}leepsilon$<\/span>, the solution\u00a0$x^{sharp}$<\/span>\u00a0to\u00a0$({rm P}_2)$\u00a0<\/span>obeys\u00a0$$ vert x^{sharp}-x_0vert_{l_{2}}le C_{S}cdotepsilon, $$<\/span>\u00a0where the constant\u00a0$C_S$<\/span>\u00a0depends only on\u00a0$delta_{4S}$<\/span>. For reasonable values of\u00a0$delta_{4S}$<\/span>,\u00a0$C_S$<\/span>\u00a0is well behaved; for example,\u00a0$C_Sapprox8.82$<\/span>\u00a0for\u00a0$delta_{4S}=frac{1}{5}$<\/span>\u00a0and\u00a0$C_{S}approx 10.47$<\/span>\u00a0for\u00a0$delta_{4S}=frac{1}{4}$<\/span>.<\/p>\n

Theorem 2. Suppose that\u00a0$x_0$<\/span>\u00a0is an arbitrary vector in\u00a0$Bbb{R}^m$<\/span>, and let\u00a0$x_{0,S}$<\/span>\u00a0be the truncated vector corresponding to the\u00a0$S$<\/span>\u00a0largest values of\u00a0$x_0$<\/span>\u00a0(in absolute value). Under the hypotheses of Theorem 1 in the paper, the solution\u00a0$x^{sharp}$<\/span>\u00a0to\u00a0$({rm P}_{2})$<\/span>\u00a0obeys\u00a0$$ Vert x^{sharp}-x_0Vert_{l_{2}}le C_{1,S}cdotepsilon+ C_{2,S}cdotfrac{Vert x_0-x_{0,S}Vert_{l_{1}}}{sqrt{S}}. $$<\/span><\/p>\n

For reasonable values of\u00a0$delta_{4S}$<\/span>, the constants in the equation labelled 1.4 in the paper are well behaved; for example,\u00a0$C_{1,S}approx 12.04$<\/span>\u00a0and\u00a0$C_{2,S}approx8.77$<\/span>\u00a0for\u00a0$delta_{4S}=frac{1}{5}$<\/span>.<\/p>\n

Reviewed by\u00a0Brody Dylan Johnson<\/a><\/span><\/p>\n

<\/div>","protected":false},"excerpt":{"rendered":"

Emmanuel Cand\u00e8s has won a prestigious MacArthur Fellowship.\u00a0 The official announcement is here.\u00a0 The LA Times has a nice write-up.\u00a0 \u00a0Both the Los Angeles Times and the MacArthur announcement highlight Cand\u00e8s’s work on compressed sensing.\u00a0 Terry Tao has a spot-on … Continue reading →<\/span><\/a><\/p>\n

<\/div>\n","protected":false},"author":86,"featured_media":2000,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[40,8],"tags":[],"class_list":["post-1799","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-announcements","category-mathematicians"],"jetpack_featured_media_url":"https:\/\/blogs.ams.org\/beyondreviews\/files\/2018\/03\/Emmanuel_Cand\u00e8s.jpg","jetpack_shortlink":"https:\/\/wp.me\/p6C2KK-t1","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts\/1799","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/users\/86"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/comments?post=1799"}],"version-history":[{"count":14,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts\/1799\/revisions"}],"predecessor-version":[{"id":2017,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts\/1799\/revisions\/2017"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/media\/2000"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/media?parent=1799"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/categories?post=1799"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/tags?post=1799"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}