×

On recovery guarantees for one-bit compressed sensing on manifolds. (English) Zbl 1462.94013

Summary: 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.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
94A14 Modulation and demodulation in information and communication theory
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahmed, A.; Recht, B.; Romberg, J., Blind deconvolution using convex programming, IEEE Trans. Inform. Theory, 60, 3, 1711-1732 (2014) · Zbl 1360.94057 · doi:10.1109/TIT.2013.2294644
[2] Ai, A.; Lapanowski, A.; Plan, Y.; Vershynin, R., One-bit compressed sensing with non-Gaussian measurements, Linear Algebra Appl., 441, 222-239 (2014) · Zbl 1332.94041 · doi:10.1016/j.laa.2013.04.002
[3] Allard, WK; Chen, G.; Maggioni, M., Multi-scale geometric methods for data sets II: geometric multi-resolution analysis, Appl. Comput. Harmon. Anal., 32, 3, 435-462 (2012) · Zbl 1242.42038 · doi:10.1016/j.acha.2011.08.001
[4] Bandyopadhyay, S.; Giannella, C.; Maulik, U.; Kargupta, H.; Liu, K.; Datta, S., Clustering distributed data streams in peer-to-peer environments, Inform. Sci., 176, 14, 1952-1985 (2006) · doi:10.1016/j.ins.2005.11.007
[5] Baraniuk, RG; Wakin, MB, Random projections of smooth manifolds, Found. Comput. Math., 9, 1, 51-77 (2009) · Zbl 1172.53005 · doi:10.1007/s10208-007-9011-z
[6] Benedetto, JJ; Powell, AM; Yılmaz, Ö., Sigma-Delta \(( \Sigma \Delta )\) quantization and finite frames, IEEE Trans. Inform. Theory, 52, 5, 1990-2005 (2006) · Zbl 1285.94014 · doi:10.1109/TIT.2006.872849
[7] Benedetto, JJ; Powell, AM; Yılmaz, Ö., Second-order sigma-delta \((\Sigma \Delta )\) quantization of finite frame expansions, Appl. Comput. Harmon. Anal., 20, 1, 126-148 (2006) · Zbl 1088.42018 · doi:10.1016/j.acha.2005.04.003
[8] Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: 23rd International Conference on Machine Learning (Pittsburgh 2006), pp. 97-104. ACM, New York (2006)
[9] Boufounos, P.T., Jacques, L., Krahmer, F., Saab, R.: Quantization and compressive sensing. In: Compressed Sensing and its Applications. Appl. Numer. Harmon. Anal., pp. 193-237. Springer, Cham (2015) · Zbl 1333.94016
[10] Candès, EJ; Romberg, JK; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59, 8, 1207-1223 (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124
[11] Candès, EJ; Strohmer, T.; Voroninski, V., PhaseLift: exact and stable signal recovery from magnitude measurements via convex programming, Commun. Pure Appl. Math., 66, 8, 1241-1274 (2013) · Zbl 1335.94013 · doi:10.1002/cpa.21432
[12] Chen, G., Iwen, M., Chin, S., Maggioni, M.: A fast multiscale framework for data in high-dimensions: measure estimation, anomaly detection, and compressive measurements. In: Visual Communications and Image Processing (San Diego 2012). IEEE, New York (2013)
[13] Dirksen, S., Iwen, M., Krause-Solberg, S., Maly, J.: Robust one-bit compressed sensing with manifold data. In: 13th International Conference on Sampling Theory and Applications (Bordeaux 2019). IEEE, New York (2019)
[14] Dirksen, S., Jung, H.Ch., Rauhut, H.: One-bit compressed sensing with partial Gaussian circulant matrices. Inf. Inference 9(3), 601-626 (2020) · Zbl 1470.94037
[15] Donoho, DL, Compressed sensing, IEEE Trans. Inform. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[16] Dudley, R.M.: V.N. Sudakov’s work on expected suprema of Gaussian processes. In: High Dimensional Probability VII (Cargèse 2014). Progr. Probab., vol. 71, pp. 37-43. Springer, Cham (2016) · Zbl 1355.60047
[17] Eftekhari, A.; Wakin, MB, New analysis of manifold embeddings and signal recovery from compressive measurements, Appl. Comput. Harmon. Anal., 39, 1, 67-109 (2015) · Zbl 1345.94013 · doi:10.1016/j.acha.2014.08.005
[18] Eldar, YC; Mishali, M., Robust recovery of signals from a structured union of subspaces, IEEE Trans. Inform. Theory, 55, 11, 5302-5316 (2009) · Zbl 1367.94087 · doi:10.1109/TIT.2009.2030471
[19] Federer, H., Curvature measures, Trans. Am. Math. Soc., 93, 3, 418-491 (1959) · Zbl 0089.38402 · doi:10.1090/S0002-9947-1959-0110078-1
[20] Feng, J.; Krahmer, F., An RIP-based approach to \(\Sigma \Delta\) quantization for compressed sensing, IEEE Signal Process. Lett., 21, 11, 1351-1355 (2014) · doi:10.1109/LSP.2014.2336700
[21] Feng, J.M., Krahmer, F., Saab, R.: Quantized compressed sensing for partial random circulant matrices. Appl. Comput. Harmon. Anal. 47(3), 1014-1032 (2019) · Zbl 1422.94011
[22] Gray, R., Oversampled sigma-delta modulation, IEEE Trans. Commun., 35, 5, 481-489 (1987) · Zbl 0641.94005 · doi:10.1109/TCOM.1987.1096814
[23] Güntürk, CS; Lammers, M.; Powell, AM; Saab, R.; Yılmaz, Ö., Sobolev duals for random frames and \(\Sigma \Delta\) quantization of compressed sensing measurements, Found. Comput. Math., 13, 1, 1-36 (2013) · Zbl 1273.41020 · doi:10.1007/s10208-012-9140-x
[24] Haghighatshoar, S.; Caire, G., Low-complexity massive MIMO subspace estimation and tracking from low-dimensional projections, IEEE Trans. Signal Process., 66, 7, 1832-1844 (2018) · Zbl 1414.94793 · doi:10.1109/TSP.2018.2795560
[25] Huynh, T.; Saab, R., Fast binary embeddings and quantized compressed sensing with structured matrices, Commun. Pure Appl. Math., 73, 1, 110-149 (2020) · Zbl 1452.94016 · doi:10.1002/cpa.21850
[26] Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: 30th Annual ACM Symposium on Theory of Computing (Dallas 1998), pp. 604-613. ACM, New York (1999) · Zbl 1029.68541
[27] Iwen, MA; Krahmer, F., Fast subspace approximation via greedy least-squares, Constr. Approx., 42, 2, 281-301 (2015) · Zbl 1406.65012 · doi:10.1007/s00365-014-9273-z
[28] Iwen, M.A., Lybrand, E., Nelson, A.A., Saab, R.: New algorithms and improved guarantees for one-bit compressed sensing on manifolds. In: 13th International Conference on Sampling Theory and Applications (Bordeaux 2019). IEEE, New York (2019)
[29] Iwen, MA; Maggioni, M., Approximation of points on low-dimensional manifolds via random linear projections, Inf. Inference, 2, 1, 1-31 (2013) · Zbl 1354.94013 · doi:10.1093/imaiai/iat001
[30] Iwen, MA; Ong, BW, A distributed and incremental SVD algorithm for agglomerative data analysis on large networks, SIAM J. Matrix Anal. Appl., 37, 4, 1699-1718 (2016) · Zbl 1349.15041 · doi:10.1137/16M1058467
[31] Jacques, L.; Laska, JN; Boufounos, PT; Baraniuk, RG, Robust \(1\)-bit compressive sensing via binary stable embeddings of sparse vectors, IEEE Trans. Inform. Theory, 59, 4, 2082-2102 (2013) · Zbl 1364.94130 · doi:10.1109/TIT.2012.2234823
[32] Jung, H.Ch., Maly, J., Palzer, L., Stollenwerk, A.: Quantized compressed sensing by rectified linear units. Proc. Appl. Math. Mech. (2021). doi:10.1002/pamm.202000015
[33] Krahmer, F.; Saab, R.; Yılmaz, Ö., Sigma-Delta quantization of sub-Gaussian frame expansions and its application to compressed sensing, Inf. Inference, 3, 1, 40-58 (2014) · Zbl 1308.94034 · doi:10.1093/imaiai/iat007
[34] Krause-Solberg, S., Maly, J.: A tractable approach for one-bit Compressed Sensing on manifolds. In: 12th International Conference on Sampling Theory and Applications (Tallinn 2017), pp. 667-671. IEEE, New York (2017)
[35] Latorre, F., Eftekhari, A., Cevher, V.: Fast and provable ADMM for learning with generative priors. In: 33rd Conference on Neural Information Processing Systems (Vancouver 2019), pp. 12027-12039. Curran Associates, Red Hook (2019)
[36] LeCun, Y., Cortes, C., Burges, Ch.J.C.: THE MNIST DATABASE of handwritten digits. http://yann.lecun.com/exdb/mnist/
[37] Liao, W.; Maggioni, M., Adaptive geometric multiscale approximations for intrinsically low-dimensional data, J. Mach. Learn. Res., 20, # 98 (2019) · Zbl 1446.68140
[38] Maggioni, M.; Minsker, S.; Strawn, N., Multiscale dictionary learning: non-asymptotic bounds and robustness, J. Mach. Learn. Res., 17, # 2 (2016) · Zbl 1360.68692
[39] Mondal, B.; Dutta, S.; Heath, RW Jr, Quantization on the Grassmann manifold, IEEE Trans. Signal Process., 55, 8, 4208-4216 (2007) · Zbl 1390.94309 · doi:10.1109/TSP.2007.896112
[40] Norsworthy, SR; Schreier, R.; Temes, GC, Delta-Sigma-Converters. Design and Simulation (1996), New York: IEEE, New York · doi:10.1109/9780470544358
[41] Plan, Y.; Vershynin, R., Robust \(1\)-bit compressed sensing and sparse logistic regression: a convex programming approach, IEEE Trans. Inform. Theory, 59, 1, 482-494 (2013) · Zbl 1364.94153 · doi:10.1109/TIT.2012.2207945
[42] Plan, Y.; Vershynin, R., One-bit compressed sensing by linear programming, Commun. Pure Appl. Math., 66, 8, 1275-1297 (2013) · Zbl 1335.94018 · doi:10.1002/cpa.21442
[43] Plan, Y.; Vershynin, R., Dimension reduction by random hyperplane tessellations, Discrete Comput. Geom., 51, 2, 438-461 (2014) · Zbl 1296.52014 · doi:10.1007/s00454-013-9561-6
[44] Recht, B.; Fazel, M.; Parrilo, PA, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321 · doi:10.1137/070697835
[45] Saab, R.; Wang, R.; Yılmaz, Ö., Quantization of compressive samples with stable and robust recovery, Appl. Comput. Harmon. Anal., 44, 1, 123-143 (2018) · Zbl 1375.94079 · doi:10.1016/j.acha.2016.04.005
[46] Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47. Cambridge University Press, Cambridge (2018) · Zbl 1430.60005
[47] Xiao, H., Rasul, K., Vollgraf, R.: Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms (2017). arXiv:1708.07747
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.