Abstract

The 1-bit compressive sensing (CS) framework is an effective method

for approximating high-dimensional signals using binary measurements. However,

deploying 1-bit CS in decentralized networks presents significant challenges due

to the discontinuity of the sign function, susceptibility to sign flips, and the

heterogeneity of network environments. Existing approaches often fail to adapt

to decentralized settings, where communication with a central coordinator is

prohibited, and only local, neighbor-to-neighbor interactions are feasible, driven

by privacy and communication cost concerns. This paper introduces an efficient

decentralized estimation approach for 1-bit CS. We reformulate the 1-bit CS

problem as a penalized least squares task, which enables us to develop a generalized

alternating direction method of multipliers algorithm with a simple implementation

for optimization. We provide rigorous algorithmic and statistical guarantees. The

proposed algorithm achieves linear convergence and, after a finite number of

communications, attains a near-oracle statistical rate of convergence. Additionally,

it reliably recovers the signal support under mild conditions. Extensive numerical

studies demonstrate the efficacy of the proposed method.

Information

Preprint No.SS-2024-0329
Manuscript IDSS-2024-0329
Complete AuthorsCanyi Chen, Zhengtian Zhu, Liping Zhu
Corresponding AuthorsLiping Zhu
Emailszhu.liping@ruc.edu.cn

References

  1. Arjoune, Y., N. Kaabouch, H. El Ghazi, and A. Tamtaoui (2018, July). A performance comparison of measurement matrices in compressive sensing. International Journal of Communication Systems 31(10).
  2. Boufounos, P. T. and R. G. Baraniuk (2008). 1-bit compressive sensing. In 2008 42nd Annual Conference on Information Sciences and Systems, pp. 16–21.
  3. Boyd, S. (2010). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine Learning 3(1), 1–122.
  4. Candes, E. J., J. K. Romberg, and T. Tao (2006). Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences 59(8), 1207–1223.
  5. Candes, E. J. and T. Tao (2005). Decoding by linear programming. IEEE Transactions on Information Theory 51(12), 4203–4215.
  6. Chang, T.-H., M. Hong, and X. Wang (2014, February). Multi-Agent Distributed Optimization via Inexact Consensus ADMM. IEEE Transactions on Signal Processing 63.
  7. Chen, C. and L. Zhu (2023). Distributed Decoding From Heterogeneous 1-Bit Compressive Measurements. Journal of Computational and Graphical Statistics 32(3), 884–894.
  8. Cook, R. D. (1998). Regression Graphics: Ideas for Studying Regressions Through Graphics (1 ed.). Wiley series in probability and statistics. Probability and statistics section. New York and Chichester: Wiley.
  9. Dai, D.-Q., L. Shen, Y. Xu, and N. Zhang (2016). Noisy 1-bit compressive sensing: models and algorithms. Applied and Computational Harmonic Analysis 40(1), 1–32.
  10. Deng, W. and W. Yin (2016, March). On the Global and Linear Convergence of the Generalized
  11. Alternating Direction Method of Multipliers. Journal of Scientific Computing 66(3), 889–916.
  12. Diaconis, P. and D. Freedman (1984). Asymptotics of graphical projection pursuit. The Annals of Statistics 12(3), 793–815.
  13. Donoho, D. L. (2006). Compressed sensing. IEEE Transactions on Information Theory 52(4), 1289–1306.
  14. Fan, J. and R. Li (2001). Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American Statistical Association 96(456), 1348–1360.
  15. Genzel, M. and P. Jung (2019). Recovering structured data from superimposed non-linear measurements. IEEE Transactions on Information Theory 66(1), 453–477.
  16. Gu, Y., J. Fan, L. Kong, S. Ma, and H. Zou (2018, July). ADMM for high-dimensional sparse penalized quantile regression. Technometrics 60(3), 319–331.
  17. Hall, P. and K.-C. Li (1993, June). On almost linearity of low dimensional projections from high dimensional data. The Annals of Statistics 21(2), 867–889.
  18. Hastie, T., R. Tibshirani, and M. Wainwright (2015). Statistical Learning with Sparsity: The Lasso and Generalizations (1st ed.). Chapman & Hall/CRC monographs on statistics & applied probability. Boca Raton: Chapman & Hall/CRC.
  19. Hector, E. C. and P. X.-K. Song (2020). Doubly distributed supervised learning and inference with high-dimensional correlated outcomes. The Journal of Machine Learning Research 21(1), 173:6983–173:7017.
  20. Hector, E. C. and P. X.-K. Song (2021, April). A Distributed and Integrated Method of Moments for High-Dimensional Correlated Data Analysis. Journal of the American Statistical Association 116(534), 805–818.
  21. Huang, J., Y. Jiao, X. Lu, and L. Zhu (2018, January). Robust decoding from 1-bit compressive sampling with ordinary and regularized least squares. SIAM Journal on Scientific Computing 40(4), A2062–A2086.
  22. Ito, K. and B. Jin (2015). Inverse Problems: Tikhonov Theory and Algorithms. World Scientific.
  23. Jacques, L., K. Degraux, and C. de Vleeschouwer (2013). Quantized iterative hard thresholding: Bridging 1-bit and high-resolution quantized compressed sensing. arXiv preprint arXiv:1305.1786.
  24. Ji, Y., G. Scutari, Y. Sun, and H. Honnappa (2023, August). Distributed (atc) gradient descent for high dimension sparse regression. IEEE Transactions on Information Theory 69(8), 5253–5276.
  25. Knudson, K., R. Saab, and R. Ward (2016). One-bit compressive sensing with norm estimation. IEEE Transactions on Information Theory 62(5), 2748–2758.
  26. Laska, J. N., Z. Wen, W. Yin, and R. G. Baraniuk (2011). Trust, but verify: Fast and accurate signal recovery from 1-bit compressive measurements. IEEE Transactions on Signal Processing 59(11), 5289–5301.
  27. Li, K.-C. (1991). Sliced inverse regression for dimension reduction. Journal of the American Statistical Association 86(414), 316–327.
  28. Li, K.-C. and N. Duan (1989). Regression Analysis Under Link Violation. The Annals of Statistics 17(3), 1009–1052.
  29. Li, Z., W. Shi, and M. Yan (2019, September). A Decentralized Proximal-Gradient Method With
  30. Network Independent Step-Sizes and Separated Convergence Rates. IEEE Transactions on Signal Processing 67(17), 4494–4506.
  31. Ling, Q. and Z. Tian (2010, July). Decentralized Sparse Signal Recovery for Compressive Sleeping
  32. Wireless Sensor Networks. IEEE Transactions on Signal Processing 58(7), 3816–3827.
  33. Liu, W., D. Gong, and Z. Xu (2016). One-bit compressed sensing by greedy algorithms. Numerical Mathematics: Theory, Methods and Applications 9(2), 169–184.
  34. Liu, W., X. Mao, and X. Zhang (2022). Fast and Robust Sparsity Learning Over Networks: A Decentralized Surrogate Median Regression Approach. IEEE Transactions on Signal Processing 70, 797–809.
  35. Ma, S. and J. Huang (2017). A concave pairwise fusion approach to subgroup analysis. Journal of the American Statistical Association 112(517), 410–423.
  36. Ma, Y. and L. Zhu (2012, March). A semiparametric approach to dimension reduction. Journal of the American Statistical Association 107(497), 168–179.
  37. Mallat, S. (1999). A Wavelet Tour of Signal Processing. Elsevier.
  38. Maly, J. and L. Palzer (2019). Analysis of hard-thresholding for distributed compressed sensing with one-bit measurements. Information and Inference: A Journal of the IMA.
  39. Nedic, A. and A. Ozdaglar (2009, January). Distributed Subgradient Methods for Multi-Agent
  40. Optimization. IEEE Transactions on Automatic Control 54(1), 48–61.
  41. Qiao, N. and C. Chen (2024). Fast and robust low-rank learning over networks: A decentralized matrix quantile regression approach. Journal of Computational and Graphical Statistics.
  42. Rani, M., S. B. Dhok, and R. B. Deshmukh (2018). A systematic review of compressive sensing: Concepts, implementations and applications. IEEE Access 6, 4875–4894.
  43. Shannon, C. (1949, January). Communication in the Presence of Noise. Proceedings of the IRE 37(1), 10–21.
  44. Shi, W., Q. Ling, G. Wu, and W. Yin (2015). A Proximal Gradient Algorithm for Decentralized Composite Optimization. IEEE Transactions on Signal Processing 63(22), 6013–6023.
  45. Shi, W., Q. Ling, K. Yuan, G. Wu, and W. Yin (2014, April). On the Linear Convergence of the ADMM in Decentralized Consensus Optimization. IEEE Transactions on Signal Processing 62(7), 1750–1761.
  46. Stein, C. M. (1981). Estimation of the Mean of a Multivariate Normal Distribution. The Annals of Statistics 9(6), 1135–1151.
  47. Sun, Y., P. Babu, and D. P. Palomar (2017, February). Majorization-Minimization Algorithms in
  48. Signal Processing, Communications, and Machine Learning. IEEE Transactions on Signal Processing 65(3), 794–816.
  49. Tang, L., L. Zhou, and P. X.-K. Song (2020, March). Distributed simultaneous inference in generalized linear models via confidence distribution. Journal of Multivariate Analysis 176, 104567.
  50. Tao, S., D. Boley, and S. Zhang (2016, January). Local Linear Convergence of ISTA and FISTA on the LASSO Problem. SIAM Journal on Optimization 26(1), 313–336.
  51. Wainwright, M. J. (2009). Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ1-constrained quadratic programming (lasso). IEEE Transactions on Information Theory 55(5), 2183–2202.
  52. Wang, H., B. Li, and C. Leng (2009, June). Shrinkage tuning parameter selection with a diverging number of parameters.
  53. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 71(3), 671–683.
  54. Wang, H. and C. Li (2018, June). Distributed Quantile Regression Over Sensor Networks. IEEE
  55. Transactions on Signal and Information Processing over Networks 4(2), 338–348.
  56. Wang, H., L. Xia, and C. Li (2019, April). Distributed online quantile regression over networks with quantized communication. Signal Processing 157, 141–150.
  57. Xia, Y. (2007, December). A constructive approach to the estimation of dimension reduction directions. Annals of Statistics 35(6), 2654–2690.
  58. Yan, M., Y. Yang, and S. Osher (2012). Robust 1-bit compressive sensing using adaptive outlier pursuit. IEEE Transactions on Signal Processing 60(7), 3868–3875.
  59. Yaskov, P. (2014, September). Lower bounds on the smallest eigenvalue of a sample covariance matrix. Electronic Communications in Probability 19.
  60. Yuan, K., Q. Ling, and W. Yin (2016, January). On the convergence of decentralized gradient descent. SIAM Journal on Optimization 26(3), 1835–1854.
  61. Zhang, C.-H. (2010). Nearly unbiased variable selection under minimax concave penalty. The Annals of Statistics 38(2), 894–942.
  62. Zhang, J., K. You, and T. Ba¸sar (2019, June). Distributed Discrete-Time Optimization in
  63. Multiagent Networks Using Only Sign of Relative State. IEEE Transactions on Automatic Control 64(6), 2352–2367.
  64. Zhou, L., X. She, and P. X.-K. Song (2024). Distributed Empirical Likelihood Approach to Integrating Unbalanced Datasets. Statistica Sinica.
  65. Zhu, L.-P. and L.-X. Zhu (2009). On distribution-weighted partial least squares with diverging number of highly correlated predictors. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 71(2), 525–548.
  66. Zhu, L.-P., L.-X. Zhu, and Z.-H. Feng (2010, December).
  67. Dimension reduction in regressions through cumulative slicing estimation. Journal of the American Statistical Association 105(492), 1455–1466.
  68. Zhu, Y. (2017, January). An Augmented ADMM Algorithm With Application to the Generalized
  69. Lasso Problem. Journal of Computational and Graphical Statistics 26(1), 195–204.
  70. Zou, H. and R. Li (2008, August). One-step sparse estimates in nonconcave penalized likelihood models. The Annals of Statistics 36(4), 1509–1533.

Acknowledgments

this paper; their names are listed alphabetically. Liping Zhu is supported

by the National Key R&D Program of China (2023YFA1008702) and the

National Natural Science Foundation of China (12225113 and 12171477).

Zhengtian Zhu is supported by the National Natural Science Foundation of

China (12501411), and partially supported by National Key R&D Program

of China (2024YFA1015700).