On Recovery Guarantees for One-Bit Compressed Sensing on Manifolds
Open Access
- 15 April 2021
- journal article
- research article
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 65 (4) , 953-998
Abstract
This paper studies the problem of recovering a signal from one-bit compressed sensing measurements under a manifold model; that is, assuming that the signal lies on or near a manifold of low intrinsic dimension. We provide a convex recovery method based on the Geometric Multi-Resolution Analysis and prove recovery guarantees with a near-optimal scaling in the intrinsic manifold dimension. Our method is the first tractable algorithm with such guarantees for this setting. The results are complemented by numerical experiments confirming the validity of our approach.Keywords
All Related Versions
Funding Information
- National Science Foundation (NSF DMS-1416752)
- Deutsche Forschungsgemeinschaft (August-Wilhelm Scheer Visiting Professor at TUM)
- Deutsche Forschungsgemeinschaft (SPP 1798, SFB Transregio 109)
- Deutsche Forschungsgemeinschaft (SFB Transregio 109, KR 4512/1-1)
- Deutsche Forschungsgemeinschaft (KR 4512/1-1)
This publication has 41 references indexed in Scilit:
- One‐Bit Compressed Sensing by Linear ProgrammingCommunications on Pure and Applied Mathematics, 2013
- PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex ProgrammingCommunications on Pure and Applied Mathematics, 2012
- Sobolev Duals for Random Frames and ΣΔ Quantization of Compressed Sensing MeasurementsFoundations of Computational Mathematics, 2012
- Multi-scale geometric methods for data sets II: Geometric Multi-Resolution AnalysisApplied and Computational Harmonic Analysis, 2012
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm MinimizationSIAM Review, 2010
- Random Projections of Smooth ManifoldsFoundations of Computational Mathematics, 2007
- Clustering distributed data streams in peer-to-peer environmentsInformation Sciences, 2006
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Second-order Sigma–Delta (ΣΔ) quantization of finite frame expansionsApplied and Computational Harmonic Analysis, 2006
- Curvature measuresTransactions of the American Mathematical Society, 1959