BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CREST - ECPv5.1.3//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:CREST
X-ORIGINAL-URL:https://crest.science
X-WR-CALDESC:Events for CREST
BEGIN:VTIMEZONE
TZID:Europe/Helsinki
BEGIN:DAYLIGHT
TZOFFSETFROM:+0200
TZOFFSETTO:+0300
TZNAME:EEST
DTSTART:20210328T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0300
TZOFFSETTO:+0200
TZNAME:EET
DTSTART:20211031T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Helsinki:20210913T140000
DTEND;TZID=Europe/Helsinki:20210913T151500
DTSTAMP:20260712T031530
CREATED:20210817T111444Z
LAST-MODIFIED:20210917T102249Z
UID:12940-1631541600-1631546100@crest.science
SUMMARY:Cheng Mao (Georgia Tech) - "Optimal Sparse Recovery of a Planted Vector in a Subspace"
DESCRIPTION:Statistical Seminar: Every Monday at 2:00 pm.\nTime: 2:00 pm – 3:15 pm\nDate: 13th of September 2021\nPlace: en visio \nCheng Mao (Georgia Tech)  – “Optimal Sparse Recovery of a Planted Vector in a Subspace” \nAbstract: We consider the task of recovering a pN-sparse vector planted in an n-dimensional random subspace of R^N\, given an arbitrary basis for the subspace. We give an improved analysis of (a slight variant of) a spectral method proposed by Hopkins\, Schramm\, Shi\, and Steurer (STOC 2016)\, showing that it succeeds when np << sqrt(N). This condition improves upon the best known guarantees of any polynomial-time algorithm. Our analysis also applies to the dense case p=1\, provided that the planted vector has entries sufficiently different from Gaussian. Furthermore\, we give a matching lower bound\, showing that when np >> sqrt(N)\, a general class of spectral methods fail to detect the planted vector. This yields a tight characterization of the power of this class of spectral methods and may suggest that no polynomial-time algorithm can succeed when np >> sqrt(N). \nOrganizers:\nCristina BUTUCEA (CREST)\, Alexandre TSYBAKOV (CREST)\, Karim LOUNICI (CMAP) \, Jaouad MOURTADA (CREST)\nSponsors:\nCREST-CMAP \n\n
URL:https://crest.science/event/cheng-mao-georgia-tech-tba/
CATEGORIES:Statistics
ATTACH;FMTTYPE=:
END:VEVENT
END:VCALENDAR