# American Institute of Mathematical Sciences

• Previous Article
Fast algorithms for robust principal component analysis with an upper bound on the rank
• IPI Home
• This Issue
• Next Article
Some worst-case datasets of deterministic first-order methods for solving binary logistic regression
February  2021, 15(1): 79-107. doi: 10.3934/ipi.2020066

## Stochastic greedy algorithms for multiple measurement vectors

 1 Department of Mathematics, University of Kentucky, Lexington, KY 40506 2 Department of Mathematics, University of California, Los Angeles, CA 90095 3 Department of Mathematics, University of California, Irvine, CA 92697 4 Department of Mathematics, Wofford College, Spartanburg, SC 29303 5 Center for Outcomes Research and Evaluation, Yale University, New Haven, CT 06511 6 Spiceworks, Austin, TX 78746

* Corresponding author: Jing Qin

Received  December 2019 Revised  July 2020 Published  February 2021 Early access  November 2020

Sparse representation of a single measurement vector (SMV) has been explored in a variety of compressive sensing applications. Recently, SMV models have been extended to solve multiple measurement vectors (MMV) problems, where the underlying signal is assumed to have joint sparse structures. To circumvent the NP-hardness of the $\ell_0$ minimization problem, many deterministic MMV algorithms solve the convex relaxed models with limited efficiency. In this paper, we develop stochastic greedy algorithms for solving the joint sparse MMV reconstruction problem. In particular, we propose the MMV Stochastic Iterative Hard Thresholding (MStoIHT) and MMV Stochastic Gradient Matching Pursuit (MStoGradMP) algorithms, and we also utilize the mini-batching technique to further improve their performance. Convergence analysis indicates that the proposed algorithms are able to converge faster than their SMV counterparts, i.e., concatenated StoIHT and StoGradMP, under certain conditions. Numerical experiments have illustrated the superior effectiveness of the proposed algorithms over their SMV counterparts.

Citation: Jing Qin, Shuang Li, Deanna Needell, Anna Ma, Rachel Grotheer, Chenxi Huang, Natalie Durgin. Stochastic greedy algorithms for multiple measurement vectors. Inverse Problems and Imaging, 2021, 15 (1) : 79-107. doi: 10.3934/ipi.2020066
##### References:

show all references

##### References:
Comparison of BCStoIHT and BMStoIHT for various sparsity levels of the signal matrix. From left to right: batch sizes are 1 and 10
Comparison of BCStoIHT and BMStoIHT for various numbers of signals to be reconstructed. From left to right: batch sizes are 1 and 10
Comparison of BCStoIHT and BMStoIHT for various noise levels to the measurement matrix. From left to right: batch sizes are 1 and 10
Comparison of BCStoGradMP and BMStoGradMP with various sparsity levels. From left to right: batch sizes are 1 and 10
Comparison of BCStoGradMP and BMStoGradMP with various numbers of signals. From left to right: batch sizes are 1 and 10
Comparison of BCStoGradMP and BMStoGradMP with various noise levels. From left to right: batch sizes are 1 and 10
(a) K-SVD dictionary learned from the total 75 frames from the candle video. (b) Support of sparse coefficient matrix for extracted 11 frames. The sparse coefficient matrix has non-zero entries on white area. (c-d) Some columns of the learned K-SVD dictionary
Comparison of the proposed algorithms and other MMV algorithms
 Method Error Runtime (sec.) BMStoIHT $5.64\times10^{-7}$ 0.0184 BMStoGradMP $1.05\times10^{-15}$ 0.0023 M-FOCUSS $3.80\times 10^{-3}$ 0.0190 M-OMP $7.45\times 10^{-16}$ 0.0492 M-SP $6.17\times 10^{-16}$ 0.0217 M-CoSaMP $8.22\times 10^{-16}$ 0.0218 M-HTP $5.33\times 10^{-16}$ 0.0912
 Method Error Runtime (sec.) BMStoIHT $5.64\times10^{-7}$ 0.0184 BMStoGradMP $1.05\times10^{-15}$ 0.0023 M-FOCUSS $3.80\times 10^{-3}$ 0.0190 M-OMP $7.45\times 10^{-16}$ 0.0492 M-SP $6.17\times 10^{-16}$ 0.0217 M-CoSaMP $8.22\times 10^{-16}$ 0.0218 M-HTP $5.33\times 10^{-16}$ 0.0912
Performance comparison on joint sparse video recovery
 Method Error Runtime (sec.) BMStoGradMP $3.09\times10^{-15}$ $2.56\times10^{-4}$ M-FOCUSS $3.21\times 10^{-3}$ 0.2452 M-OMP $2.51\times 10^{-16}$ 0.0743 M-SP $2.06\times 10^{-16}$ 0.1297 M-CoSaMP $4.07\times 10^{-16}$ 0.0115 M-HTP $5.72\times 10^{-2}$ 0.0134 SBC $1.19\times 10^{-8}$ $6.28\times10^{-4}$
 Method Error Runtime (sec.) BMStoGradMP $3.09\times10^{-15}$ $2.56\times10^{-4}$ M-FOCUSS $3.21\times 10^{-3}$ 0.2452 M-OMP $2.51\times 10^{-16}$ 0.0743 M-SP $2.06\times 10^{-16}$ 0.1297 M-CoSaMP $4.07\times 10^{-16}$ 0.0115 M-HTP $5.72\times 10^{-2}$ 0.0134 SBC $1.19\times 10^{-8}$ $6.28\times10^{-4}$
 [1] Hong Jiang, Wei Deng, Zuowei Shen. Surveillance video processing using compressive sensing. Inverse Problems and Imaging, 2012, 6 (2) : 201-214. doi: 10.3934/ipi.2012.6.201 [2] Lingchen Kong, Naihua Xiu, Guokai Liu. Partial $S$-goodness for partially sparse signal recovery. Numerical Algebra, Control and Optimization, 2014, 4 (1) : 25-38. doi: 10.3934/naco.2014.4.25 [3] Björn Popilka, Simon Setzer, Gabriele Steidl. Signal recovery from incomplete measurements in the presence of outliers. Inverse Problems and Imaging, 2007, 1 (4) : 661-672. doi: 10.3934/ipi.2007.1.661 [4] Xiaoping Fang, Youjun Deng. Uniqueness on recovery of piecewise constant conductivity and inner core with one measurement. Inverse Problems and Imaging, 2018, 12 (3) : 733-743. doi: 10.3934/ipi.2018031 [5] Sebastian Acosta. Recovery of the absorption coefficient in radiative transport from a single measurement. Inverse Problems and Imaging, 2015, 9 (2) : 289-300. doi: 10.3934/ipi.2015.9.289 [6] Abdulkarim Hassan Ibrahim, Poom Kumam, Min Sun, Parin Chaipunya, Auwal Bala Abubakar. Projection method with inertial step for nonlinear equations: Application to signal recovery. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021173 [7] Shitao Liu. Recovery of the sound speed and initial displacement for the wave equation by means of a single Dirichlet boundary measurement. Evolution Equations and Control Theory, 2013, 2 (2) : 355-364. doi: 10.3934/eect.2013.2.355 [8] Jian-Wu Xue, Xiao-Kun Xu, Feng Zhang. Big data dynamic compressive sensing system architecture and optimization algorithm for internet of things. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1401-1414. doi: 10.3934/dcdss.2015.8.1401 [9] Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems and Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044 [10] Francesco Cordoni, Luca Di Persio. Optimal control for the stochastic FitzHugh-Nagumo model with recovery variable. Evolution Equations and Control Theory, 2018, 7 (4) : 571-585. doi: 10.3934/eect.2018027 [11] Bruno Sixou, Valentina Davidoiu, Max Langer, Francoise Peyrin. Absorption and phase retrieval with Tikhonov and joint sparsity regularizations. Inverse Problems and Imaging, 2013, 7 (1) : 267-282. doi: 10.3934/ipi.2013.7.267 [12] Amin Boumenir, Vu Kim Tuan. Recovery of the heat coefficient by two measurements. Inverse Problems and Imaging, 2011, 5 (4) : 775-791. doi: 10.3934/ipi.2011.5.775 [13] Qian Zhao, Bitao Jiang, Xiaogang Yu, Yue Zhang. Collaborative mission optimization for ship rapid search by multiple heterogeneous remote sensing satellites. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021092 [14] Fenglong Qu, Jiaqing Yang. On recovery of an inhomogeneous cavity in inverse acoustic scattering. Inverse Problems and Imaging, 2018, 12 (2) : 281-291. doi: 10.3934/ipi.2018012 [15] Vinicius Albani, Uri M. Ascher, Xu Yang, Jorge P. Zubelli. Data driven recovery of local volatility surfaces. Inverse Problems and Imaging, 2017, 11 (5) : 799-823. doi: 10.3934/ipi.2017038 [16] Wanyou Cheng, Zixin Chen, Donghui Li. Nomonotone spectral gradient method for sparse recovery. Inverse Problems and Imaging, 2015, 9 (3) : 815-833. doi: 10.3934/ipi.2015.9.815 [17] Amin Boumenir, Vu Kim Tuan, Nguyen Hoang. The recovery of a parabolic equation from measurements at a single point. Evolution Equations and Control Theory, 2018, 7 (2) : 197-216. doi: 10.3934/eect.2018010 [18] Hang Xu, Song Li. Analysis non-sparse recovery for relaxed ALASSO. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4055-4068. doi: 10.3934/cpaa.2020179 [19] Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025 [20] Victor Isakov. Recovery of time dependent volatility coefficient by linearization. Evolution Equations and Control Theory, 2014, 3 (1) : 119-134. doi: 10.3934/eect.2014.3.119

2020 Impact Factor: 1.639