American Institute of Mathematical Sciences

• Previous Article
Direct and inverse spectral problems for a star graph of Stieltjes strings damped at a pendant vertex
• IPI Home
• This Issue
• Next Article
An adaptive total variational despeckling model based on gray level indicator frame
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  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 & Imaging, 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] Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044 [2] 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 [3] Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100 [4] Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $(n, m)$-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117 [5] Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272 [6] Meilan Cai, Maoan Han. Limit cycle bifurcations in a class of piecewise smooth cubic systems with multiple parameters. Communications on Pure & Applied Analysis, 2021, 20 (1) : 55-75. doi: 10.3934/cpaa.2020257 [7] Stefan Ruschel, Serhiy Yanchuk. The spectrum of delay differential equations with multiple hierarchical large delays. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 151-175. doi: 10.3934/dcdss.2020321 [8] Fanni M. Sélley. A self-consistent dynamical system with multiple absolutely continuous invariant measures. Journal of Computational Dynamics, 2021, 8 (1) : 9-32. doi: 10.3934/jcd.2021002 [9] Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050 [10] Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115 [11] Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 [12] Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098 [13] Zhenzhen Wang, Tianshou Zhou. Asymptotic behaviors and stochastic traveling waves in stochastic Fisher-KPP equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020323 [14] Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031 [15] Yi An, Bo Li, Lei Wang, Chao Zhang, Xiaoli Zhou. Calibration of a 3D laser rangefinder and a camera based on optimization solution. Journal of Industrial & Management Optimization, 2021, 17 (1) : 427-445. doi: 10.3934/jimo.2019119 [16] Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109 [17] Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 [18] Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117 [19] Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264 [20] Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317

2019 Impact Factor: 1.373

Tools

Article outline

Figures and Tables