@article{ma_kang_silversteint_baron_2021, title={Local Convergence of an AMP Variant to the LASSO Solution in Finite Dimensions}, DOI={10.1109/ISIT45174.2021.9518079}, abstractNote={A common sparse linear regression formulation is $\ell_{1}$ regularized least squares, which is also known as least absolute shrinkage and selection operator (LASSO). Approximate message passing (AMP) has been proved to asymptotically achieve the LASSO solution when the regression matrix has independent and identically distributed (i.i.d.) Gaussian entries in the sense that the averaged per-coordinate $\ell_{2}$ distance between the AMP iterates and LASSO solution vanishes as the signal dimension goes to infinity before the iteration number. However, in finite dimensional settings, characterization of AMP iterates in the limit of large iteration number has not been established. In this work, we propose an AMP variant by including a parameter that depends on the largest singular value of the regression matrix. The proposed algorithm can also be considered as a primal dual hybrid gradient algorithm with adaptive stepsizes. We show that whenever the AMP variant converges, it converges to the LASSO solution for arbitrary finite dimensional regression matrices. Moreover, we show that our AMP variant is locally stable around the LASSO solution under the condition that the LASSO solution is unique and that the regression matrix is drawn from a continuous distribution. Our local stability result implies that when the regression matrix is large and has i.i.d. random entries, the original AMP, which is a special case of the proposed AMP variant, is locally stable around the LASSO solution.}, journal={2021 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT)}, author={Ma, Yanting and Kang, Min and Silversteint, Jack W. and Baron, Dror}, year={2021}, pages={2256–2261} }
@article{ma_rush_baron_2019, title={Analysis of Approximate Message Passing With Non-Separable Denoisers and Markov Random Field Priors}, volume={65}, ISSN={["1557-9654"]}, url={https://doi.org/10.1109/TIT.2019.2934152}, DOI={10.1109/TIT.2019.2934152}, abstractNote={Approximate message passing (AMP) is a class of low-complexity, scalable algorithms for solving high-dimensional linear regression tasks where one wishes to recover an unknown signal from noisy, linear measurements. AMP is an iterative algorithm that performs estimation by updating an estimate of the unknown signal at each iteration and the performance of AMP (quantified, for example, by the mean squared error of its estimates) depends on the choice of a “denoiser” function that is used to produce these signal estimates at each iteration. An attractive feature of AMP is that its performance can be tracked by a scalar recursion referred to as state evolution. Previous theoretical analysis of the accuracy of the state evolution predictions has been limited to the use of only separable denoisers or block-separable denoisers, a class of denoisers that underperform when sophisticated dependencies exist between signal entries. Since signals with entrywise dependencies are common in image/video-processing applications, in this work we study the high-dimensional linear regression task when the dependence structure of the input signal is modeled by a Markov random field prior distribution. We provide a rigorous analysis of the performance of AMP, demonstrating the accuracy of the state evolution predictions, when a class of non-separable sliding-window denoisers is applied. Moreover, we provide numerical examples where AMP with sliding-window denoisers can successfully capture local dependencies in images.}, number={11}, journal={IEEE TRANSACTIONS ON INFORMATION THEORY}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Ma, Yanting and Rush, Cynthia and Baron, Dror}, year={2019}, month={Nov}, pages={7367–7389} }
@inproceedings{ma_rush_baron_2017, title={Analysis of approximate message passing with a class of non-separable denoisers}, DOI={10.1109/isit.2017.8006524}, abstractNote={Approximate message passing (AMP) is a class of efficient algorithms for solving high-dimensional linear regression tasks where one wishes to recover an unknown signal βο from noisy, linear measurements y = Αβ 0 + w. When applying a separable denoiser at each iteration, the performance of AMP (for example, the mean squared error of its estimates) can be accurately tracked by a simple, scalar iteration referred to as state evolution. Although separable denoisers are sufficient if the unknown signal has independent and identically distributed entries, in many real-world applications, like image or audio signal reconstruction, the unknown signal contains dependencies between entries. In these cases, a coordinate-wise independence structure is not a good approximation to the true prior of the unknown signal. In this paper we assume the unknown signal has dependent entries, and using a class of non-separable sliding-window denoisers, we prove that a new form of state evolution still accurately predicts AMP performance. This is an early step in understanding the role of non-separable denoisers within AMP, and will lead to a characterization of more general denoisers in problems including compressive image reconstruction.}, booktitle={2017 ieee international symposium on information theory (isit)}, author={Ma, Y. T. and Rush, C. and Baron, Dror}, year={2017}, pages={231–235} }
@inproceedings{ma_liu_mansour_kamilov_taguchi_boufounos_vetro_2017, title={Fusion of multi-angular aerial images based on epipolar geometry and matrix completion}, booktitle={2017 24th ieee international conference on image processing (icip)}, author={Ma, Y. T. and Liu, D. H. and Mansour, H. and Kamilov, U. S. and Taguchi, Y. and Boufounos, P. T. and Vetro, A.}, year={2017}, pages={1197–1201} }
@article{tan_ma_rueda_baron_arce_2016, title={Compressive Hyperspectral Imaging via Approximate Message Passing}, volume={10}, ISSN={["1941-0484"]}, DOI={10.1109/jstsp.2015.2500190}, abstractNote={We consider a compressive hyperspectral imaging reconstruction problem, where three-dimensional spatio-spectral information about a scene is sensed by a coded aperture snapshot spectral imager (CASSI). The CASSI imaging process can be modeled as suppressing three-dimensional coded and shifted voxels and projecting these onto a two-dimensional plane, such that the number of acquired measurements is greatly reduced. On the other hand, because the measurements are highly compressive, the reconstruction process becomes challenging. We previously proposed a compressive imaging reconstruction algorithm that is applied to two-dimensional images based on the approximate message passing (AMP) framework. AMP is an iterative algorithm that can be used in signal and image reconstruction by performing denoising at each iteration. We employed an adaptive Wiener filter as the image denoiser, and called our algorithm "AMP-Wiener." In this paper, we extend AMP-Wiener to three-dimensional hyperspectral image reconstruction, and call it "AMP-3D-Wiener." Applying the AMP framework to the CASSI system is challenging, because the matrix that models the CASSI system is highly sparse, and such a matrix is not suitable to AMP and makes it difficult for AMP to converge. Therefore, we modify the adaptive Wiener filter and employ a technique called damping to solve for the divergence issue of AMP. Our approach is applied in nature, and the numerical experiments show that AMP-3D-Wiener outperforms existing widely-used algorithms such as gradient projection for sparse reconstruction (GPSR) and two-step iterative shrinkage/thresholding (TwIST) given a similar amount of runtime. Moreover, in contrast to GPSR and TwIST, AMP-3D-Wiener need not tune any parameters, which simplifies the reconstruction process.}, number={2}, journal={IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING}, author={Tan, Jin and Ma, Yanting and Rueda, Hoover and Baron, Dror and Arce, Gonzalo R.}, year={2016}, month={Mar}, pages={389–401} }
@inproceedings{ma_baron_beirami_2015, title={Mismatched estimation in large linear systems}, DOI={10.1109/isit.2015.7282557}, abstractNote={We study the excess mean square error (EMSE) above the minimum mean square error (MMSE) in large linear systems where the posterior mean estimator (PME) is evaluated with a postulated prior that differs from the true prior of the input signal. We focus on large linear systems where the measurements are acquired via an independent and identically distributed random matrix, and are corrupted by additive white Gaussian noise (AWGN). The relationship between the EMSE in large linear systems and EMSE in scalar channels is derived, and closed form approximations are provided. Our analysis is based on the decoupling principle, which links scalar channels to large linear system analyses. Numerical examples demonstrate that our closed form approximations are accurate.}, booktitle={2015 ieee international symposium on information theory (isit)}, author={Ma, Y. T. and Baron, Dror and Beirami, A.}, year={2015}, pages={760–764} }
@article{ma_baron_needell_2014, title={Two-Part Reconstruction With Noisy-Sudocodes}, volume={62}, ISSN={["1941-0476"]}, DOI={10.1109/tsp.2014.2362892}, abstractNote={We develop a two-part reconstruction framework for signal recovery in compressed sensing (CS), where a fast algorithm is applied to provide partial recovery in Part 1, and a CS algorithm is applied to complete the residual problem in Part 2. Partitioning the reconstruction process into two complementary parts provides a natural trade-off between runtime and reconstruction quality. To exploit the advantages of the two-part framework, we propose a Noisy-Sudocodes algorithm that performs two-part reconstruction of sparse signals in the presence of measurement noise. Specifically, we design a fast algorithm for Part 1 of Noisy-Sudocodes that identifies the zero coefficients of the input signal from its noisy measurements. Many existing CS algorithms could be applied to Part 2, and we investigate approximate message passing (AMP) and binary iterative hard thresholding (BIHT). For Noisy-Sudocodes with AMP in Part 2, we provide a theoretical analysis that characterizes the trade-off between runtime and reconstruction quality. In a 1-bit CS setting where a new 1-bit quantizer is constructed for Part 1 and BIHT is applied to Part 2, numerical results show that the Noisy-Sudocodes algorithm improves over BIHT in both runtime and reconstruction quality.}, number={23}, journal={IEEE TRANSACTIONS ON SIGNAL PROCESSING}, author={Ma, Yanting and Baron, Dror and Needell, Deanna}, year={2014}, month={Dec}, pages={6323–6334} }