Asymptotic Performance Prediction for ADMM-Based Compressed Sensing

Abstract

In this paper, we propose a method to predict the asymptotic performance of the alternating direction method of multipliers (ADMM) for compressed sensing, where we reconstruct an unknown structured signal from its underdetermined linear measurements. The derivation of the proposed method is based on the recently developed convex Gaussian min-max theorem (CGMT), which can be applied to various convex optimization problems to obtain its asymptotic error performance. Our main idea is to analyze the convex subproblem in the update of ADMM iteratively and characterize the asymptotic distribution of the tentative estimate obtained at each iteration. However, since the original CGMT cannot be used directly for the analysis of the iterative updates, we intuitively assume an extended version of CGMT in the derivation of the proposed method. Under the assumption, the result shows that the update equations in ADMM can be decoupled into a scalar-valued stochastic process in the asymptotic regime with the large system limit. From the asymptotic result, we can predict the evolution of the error (e.g., mean-square-error (MSE) and symbol error rate (SER)) in ADMM for large-scale compressed sensing problems. Simulation results show that the empirical performance of ADMM and its prediction are close to each other in sparse vector reconstruction and binary vector reconstruction.

arXiv commentaccepted to IEEE Transactions on Signal Processing

References in corpus (9)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Generalized Orthogonal Matching Pursuit
• Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems
• Universality in polytope phase transitions and message passing algorithms
• Discrete Signal Reconstruction by Sum of Absolute Values
• Symbol Error Rate Performance of Box-relaxation Decoders in Massive MIMO
• A survey on the Weierstrass approximation theorem
• Convolutional Approximate Message-Passing