Abstract
The standard sparse representation aims to reconstruct sparse signal from single measurement vector which is known as SMV model. In some applications, the SMV model extend to the multiple measurement vector (MMV) model, in which the signal consists of a set of jointly sparse vectors. In this paper, efficient algorithms based on split Bregman iteration are proposed to solve the MMV problems with both constrained form and unconstrained form. The convergence of the proposed algorithms is also discussed. Moreover, the proposed algorithms are used in magnetic resonance imaging reconstruction. Numerical results show the effectiveness of the proposed algorithms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bazerque, J. A., & Giannakis, G. B. (2010). Distributed spectrum sensing for cognitive radio networks by exploiting sparsity. IEEE Transactions on Signal Processing, 58(3), 1847–1862.
Berg, E., & Friedlander, M. (2010). Theoretical and empirical results for recovery from multiple measurements. IEEE Transactions on Information Theory, 56(5), 2516–2527.
Berg, E., Schmidt, M., Friedlander ,M. P., & Murphy, K. (2008). Group sparsity via linear-time projection. Technical Report TR-2008-09, Department of Computer Science, University of British Columbia.
Bilen, C., Wang, Y., & Selesnick, I. W. (2012). High-speed compressed sensing reconstruction in dynamic parallel MRI using augmented lagrangian and parallel processing. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2(3), 370–379.
Cai, J. F., Osher, S., & Shen, Z. (2009). Split bregman methods and frame based image restoration. Multiscale Modeling & Simulation, 8(2), 337–369.
Chen, J., & Huo, X. (2006). Theoretical results on sparse representations of multiple-measurement vectors. IEEE Transactions on Signal Processing, 54(12), 4634–4643.
Cotter, S. F., Rao, B. D., Engan, K., & Kreutz-Delgado, K. (2005). Sparse solutions to linear inverse problems with multiple measurement vectors. IEEE Transactions on Signal Processing, 53(7), 2477–2488.
Davies, M. E., & Eldar, Y. C. (2012). Rank awareness in joint sparse recovery. IEEE Transactions on Information Theory, 58(2), 1135–1146.
Deng, W., Yin, W., & Zhang, Y. (2011). Group sparse optimization by alternating direction method. TR11-06, Department of Computational and Applied Mathematics, Rice University.
Duarte, M. F., & Eldar, Y. C. (2011). Structured compressed sensing: From theory to applications. IEEE Transactions on Signal Processing, 59(9), 4053–4085.
Eldar, Y. C., Kuppinger, P., & Bolcskei, H. (2010). Block-sparse signals: Uncertainty relations and efficient recovery. IEEE Transactions on Signal Processing, 58(6), 3042–3054.
Goldstein, T., & Osher, S. (2009). The split bregman method for l1-regularized problems. SIAM Journal on Imaging Sciences, 2(2), 323–343.
He, Z., Cichocki, A., Cichocki, R., & Cao, J. (2008). CG-M-FOCUSS and its application to distributed compressed sensing. In: Advances in Neural Networks-ISNN 2008, pp. 237–245.
Huang, J., & Zhang, T. (2010). The benefit of group sparsity. The Annals of Statistics, 38(4), 1978–2004.
Jiang, L., & Yin, H. (2012). Bregman iteration algorithm for sparse nonnegative matrix factorizations via alternating l1-norm minimization. Multidimensional Systems and Signal Processing, 23(3), 315–328.
Lee, D. H., Hong, C. P., & Lee, M. W. (2013). Sparse magnetic resonance imaging reconstruction using the bregman iteration. Journal of the Korean Physical Society, 62(2), 328–332.
Lee, K., Bresler, Y., & Junge, M. (2012). Subspace methods for joint sparse recovery. IEEE Transactions on Information Theory, 58(6), 3613–3641.
Liu, B., King, K., Steckner, M., Xie, J., Sheng, J., & Ying, L. (2009a). Regularized sensitivity encoding (sense) reconstruction using bregman iterations. Magnetic Resonance in Medicine, 61(1), 145–152.
Liu, J., Ji, S., & Ye, J. (2009b). SLEP: Sparse Learning with Efficient Projections. Arizona State University.
Ma, S., Goldfarb, D., & Chen, L. (2011). Fixed point and bregman iterative methods for matrix rank minimization. Mathematical Programming, 128(1–2), 321–353.
Majumdar, A., & Ward, R. (2012) Face recognition from video: An MMV recovery approach. In: 2012 IEEE international conference on acoustics, speech and signal processing (ICASSP), IEEE, pp. 2221–2224.
Majumdar, A., & Ward, R. (2013). Rank awareness in group-sparse recovery of multi-echo mr images. Sensors, 13(3), 3902–3921.
Majumdar, A., & Ward, R. K. (2011). Joint reconstruction of multiecho mr images using correlated sparsity. Magnetic Resonance Imaging, 29(7), 899–906.
Mishali, M., & Eldar, Y. C. (2008). Reduce and boost: Recovering arbitrary sets of jointly sparse vectors. IEEE Transactions on Signal Processing, 56(10), 4692–4702.
Qin, Z., Scheinberg, K., & Goldfarb, D. (2010). Efficient block-coordinate descent algorithms for the group lasso. Technical Report 2806, Optimization Online.
Smith, D. S., Gore, J. C., Yankeelov, T. E., & Welch, E. B. (2012). Real-time compressive sensing MRI reconstruction using GPU computing and split bregman methods. International Journal of Biomedical Imaging, 2012, 1–6.
Stone, S. S., Haldar, J. P., Tsao, S. C., Sutton, B. P., Liang, Z. P., et al. (2008). Accelerating advanced MRI reconstructions on GPUs. Journal of Parallel and Distributed Computing, 68(10), 1307–1318.
Tropp, J. A. (2006). Algorithms for simultaneous sparse approximation. Part ii: Convex relaxation. Signal Processing, 86(3), 589–602.
Tropp, J. A., Gilbert, A. C., & Strauss, M. J. (2006). Algorithms for simultaneous sparse approximation. Part i: Greedy pursuit. Signal Processing, 86(3), 572–588.
Tseng, P., & Yun, S. (2009). A coordinate gradient descent method for nonsmooth separable minimization. Mathematical Programming, 117(1–2), 387–423.
Xu, J., Feng, X., & Hao, Y. (2012). A coupled variational model for image denoising using a duality strategy and split bregman. Multidimensional Systems and Signal Processing, pp. 1–12. doi:10.1007/s11045-012-0190-7.
Yin, W., Osher, S., Goldfarb, D., & Darbon, J. (2008). Bregman iterative algorithms for \(\ell 1\)-minimization with applications to compressed sensing. SIAM Journal on Imaging Sciences, 1(1), 143–168.
Yuan, M., & Lin, Y. (2006). Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68(1), 49–67.
Zou, J., Fu, Y., & Xie, S. (2012). A block fixed point continuation algorithm for block-sparse reconstruction. IEEE Signal Processing Letters, 19(6), 364–367.
Acknowledgments
This work was supported by International cooperation project of Guangdong Natural Science Foundation under Grant No. 2009B050700020, NSFC—Guangdong Union Project under Grant No. U0835003, NSFC under Grant No. 60903170, 61004054, 61104053 and 61103122.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix 1: Proof of theorem 1
proof
The main idea of this proof is from the one in Cai et al. (2009). However, this proof is much different due to the matrix variable and the mixed norm.
Since subproblems (17) and (18) are convex, the first order optimality condition of Algorithm 1 gives as follows:
where \(\mathbf P ^{k+1} \in \partial \Vert \mathbf Z \Vert _{2,1} \mid _\mathbf{Z = \mathbf Z ^{k+1} }\), for ease of notations, we just denote \(\mathbf P ^{k+1} \in \partial \Vert \mathbf Z ^{k+1} \Vert _{2,1}\) in the remainder of this paper. The subgradient of \(\Vert \cdot \Vert _{2,1}\) can be seen in Appendix 3.
Since there exists at least one solution \(\mathbf X ^*\) of (3) by the assumption, by the first order optimality condition, \(\mathbf X ^*\) must satisfy
where \(\mathbf P ^{*} \in \partial \Vert \mathbf Z ^{*} \Vert _{2,1}\) and \(\mathbf Z ^{*} = \mathbf X ^{*}\).
Let \(\mathbf B ^* = \mathbf P ^*/ \mu \). Then (35) can be formulated as
Comparing (36) with (34), \((\mathbf X ^{*}, \mathbf Z ^{*}, \mathbf B ^{*})\) is a fixed point of Algorithm 1. Similar like the paper by Goldstein and Osher (2009), if the unconstrained spilt Bregman iteration converges, it converges to a solution of (3).
Denote the errors by \(\mathbf X _e^{k} = \mathbf X ^{k}-\mathbf X ^{*}\), \(\mathbf Z _e^{k} = \mathbf Z ^{k}-\mathbf Z ^{*}\) and \(\mathbf B _e^{k} = \mathbf B ^{k}-\mathbf B ^{*}\). Subtracting the first equation of (34) by the first equation of (36), we obtain
Taking the inner product of the left- and right-hand sides with \(\mathbf X _e^{k+1}\), we have
Similarly, subtracting the second equation of (34) by the second equation of (36) and then taking the inner product of the left- and right- hand sides with \(\mathbf Z _e^{k+1}\), we have
where \(\mathbf P ^{k+1} \in \partial \Vert \mathbf Z ^{k+1} \Vert _{2,1}\), \(\mathbf P ^{*} \in \partial \Vert \mathbf Z ^{*} \Vert _{2,1}\).
Adding both sides of (38) to the corresponding sides of (39), we have
Furthermore, by subtracting the third equation of (34) by the corresponding one in (36), we obtain
Taking square norm of both sides of (41), we obtain
and further
Substituting (43) into (40), we have
Summing (44) from \(k=0\) to \(k=K\), it yields
Since \(\mathbf P ^{k+1} \in \partial \Vert \mathbf X ^{k+1} \Vert _{2,1}\), \(\mathbf P ^{*} \in \partial \Vert \mathbf X ^{*} \Vert _{2,1}\) and \(\Vert \cdot \Vert _{2,1}\) is convex, for \(\forall k\),
Therefore, all terms involved in (45) are nonnegative. We have
From (47) and \(\mu >0\), \(\lambda >0\), we can get
(48) imply that \(\lim _{k\rightarrow + \infty } \Vert \mathbf A \mathbf X _e^{k} \Vert _F^2 =0\), and
Recall the definition of the Bregman distance, for any convex function \(J\), we have
where \(\mathbf P \in \partial J(\mathbf Z )\) and \(\mathbf Q \in \partial J(\mathbf X )\).
Now let \(J(\mathbf X ) = \frac{1}{2}\Vert \mathbf{AX-Y }\Vert _F^2\), \(\nabla J(\mathbf X ) = \mathbf A ^T(\mathbf{AX-Y })\), from (50) we have
(51) together with the nonnegativity of the Bregman distance, implies that
i.e.,
Similarly, (47) also leads to
and hence
Let \(J(\mathbf Z ) = \Vert \mathbf Z \Vert _{2,1}\) and \(\mathbf P \in \partial \Vert \mathbf Z \Vert _{2,1}\), we can get \(\lim _{k\rightarrow + \infty } D_{\Vert \cdot \Vert _{2,1}}^\mathbf{P ^*}(\mathbf Z ^k,\mathbf Z ^*) =0\), i.e.,
Moreover, since \(\mu >0\), (47) also leads to \(\sum _{k=0}^{+ \infty } \Vert \mathbf X _e^{k+1} - \mathbf Z _e^{k} \Vert _F^2 < + \infty \), which implies that \(\lim _{k\rightarrow + \infty } \Vert \mathbf X _e^{k+1} - \mathbf Z _e^{k} \Vert _F^2 = 0\). By \(\mathbf X ^{*} = \mathbf Z ^{*}\), we conclude that
Since \(\Vert \cdot \Vert _{2,1}\) is continuous, by (56) and (57), for \(\mathbf X \), we have
Adding (53) to (58), it yields
where the last equality comes from (35). So (29) is proved.
Next, we prove (30) whenever (3) has a unique solution. It is proved by contradiction.
Define \(\varPhi (\mathbf X ) = \Vert \mathbf X \Vert _{2,1} + \Vert \mathbf{AX-Y }\Vert _F^2\). Then \(\varPhi (\mathbf X )\) is convex and lower semi-continuous. Since \(\mathbf X ^*\) is the unique minimizer, we have \(\varPhi (\mathbf X ^*) > \varPhi (\mathbf X )\) for \(\mathbf X \ne \mathbf X ^*\).
Now, suppose that (30) does not hold. So, there exists a subsequence \(\mathbf X ^{k_i}\) such that \(\Vert \mathbf X ^{k_i} - \mathbf X ^{*}\Vert _F > \epsilon \) for some \(\epsilon > 0\) and all \(i\). Then, \(\varPhi (\mathbf X ^{k_i}) > \min \{ \varPhi (\mathbf X ) : \Vert \mathbf X ^{k_i} - \mathbf X ^{*}\Vert _F = \epsilon \}\). Let \(\mathbf Z \) be the intersection of \(\{ \mathbf X : \Vert \mathbf X - \mathbf X ^{*}\Vert _F = \epsilon \}\) and the line from \(\mathbf X ^{*}\) to \(\mathbf X ^{k_i}\). Indeed, there exists a positive number \(t \in (0,1)\) such that \(\mathbf Z = t \mathbf X ^{*} + (1-t) \mathbf X ^{k_i}\). By the convexity of \(\varPhi \) and the definition of \(\mathbf X ^{*}\), we have
Denote \({\tilde{\mathbf{X }}} = \min \{ \varPhi (\mathbf X ) : \Vert \mathbf X ^{k_i} - \mathbf X ^{*}\Vert _F = \epsilon \}\). By (29), we have
which is a contradiction. So (30) holds whenever (3) has a unique solution. \(\square \)
Appendix 2: Proof of Theorem 2
proof
Since subproblems (26) and (27) are convex, the first order optimality condition of Algorithm 2 is given as follows:
where \(\mathbf P ^{k+1} \in \partial \Vert \mathbf Z ^{k+1} \Vert _{2,1}\).
Let \( L(\mathbf X ,\mathbf W ) = \Vert \mathbf X \Vert _{2,1} + \langle \mathbf W , \mathbf{AX-Y }\rangle \) be the Lagrangian of (2) and \(\mathbf W \) be the Lagrangian multiplier. Since there exists at least one solution \(\mathbf X ^*\) of (2) by the assumption, the KKT condition ensures the existence of a \(\mathbf W ^*\) such that
where \(\mathbf P ^{*} \in \partial \Vert \mathbf X ^{*} \Vert _{2,1}\).
Let \(\mathbf B ^* = \mathbf P ^*/ \mu \), \(\mathbf C ^* = \mathbf W ^*/ \lambda \). Then (63) can be formulated as
Comparing (64) and (62), \((\mathbf X ^{*}, \mathbf Z ^{*}, \mathbf C ^{*}, \mathbf B ^{*})\) is a fixed point of Algorithm 2.
Denote the errors by \(\mathbf X _e^{k} = \mathbf X ^{k}-\mathbf X ^{*}\), \(\mathbf Z _e^{k} = \mathbf Z ^{k}-\mathbf Z ^{*}\), \(\mathbf B _e^{k} = \mathbf B ^{k}-\mathbf B ^{*}\) and \(\mathbf C _e^{k} = \mathbf C ^{k}-\mathbf C ^{*}\).
Similar to the corresponding part of the proof of Theorem 1,
we can get
Note all terms involved in (65) are nonnegative. We have
From (66) and \(\mu >0\), \(\lambda >0\), we can get
(67) and \(\mathbf A \mathbf X _e^{k+1} = \mathbf A \mathbf X ^{k+1} - \mathbf Y \) leads to the first equation in (31) holding, i.e.,
Similarly, (67) also leads to
and hence
Recall equation (50) and let \(J(\mathbf Z )= \Vert \mathbf Z \Vert _{2,1}\), \(\mathbf P \in \partial \Vert \mathbf Z \Vert _{2,1}\), we have
(71) and (70) imply that \(\lim _{k\rightarrow + \infty } D_{\Vert \cdot \Vert _{2,1}}^\mathbf{P ^*}(\mathbf Z ^k,\mathbf Z ^*) + D_{\Vert \cdot \Vert _{2,1}}^\mathbf{P ^k}(\mathbf Z ^*,\mathbf Z ^k) =0\), and together with the nonnegativity of the Bregman distance, implies that
i.e.,
Moreover, since \(\mu >0\), (67) also leads to \(\sum _{k=0}^{+ \infty } \Vert \mathbf X _e^{k+1} - \mathbf Z _e^{k} \Vert _F^2 < + \infty \), which implies that \(\lim _{k\rightarrow + \infty } \Vert \mathbf X _e^{k+1} - \mathbf Z _e^{k} \Vert _F^2 = 0\). By \(\mathbf X ^{*} = \mathbf Z ^{*}\), we conclude that
Since \(\Vert \cdot \Vert _{2,1}\) is continuous, by (73) and (74), for \(\mathbf X \), we have
Furthermore, since \(\mathbf A \mathbf X ^k \rightarrow \mathbf Y \) and \(\mathbf A \mathbf X ^* = \mathbf Y \), we have
Summing (75) and (76), it yields
where the last equality comes from the first equation of (63). This is the second equation of (31).
Next, we prove (32) whenever (2) has a unique solution. It is proved by contradiction.
Let \(\mathbf W ^*\) be the vector in (63). Define
(78) is convex and continuous. Since \((\mathbf X ^*,\mathbf W ^*)\) is a saddle point of \(L(\mathbf X ,\mathbf W )\) and \(\mathbf A \mathbf X ^*=\mathbf Y \), we have \(\varPhi (\mathbf X ) \ge \varPhi (\mathbf X ^*)\). Especially, we have \(\varPhi (\mathbf X ) > \varPhi (\mathbf X ^*)\) for \(\mathbf X \ne \mathbf X ^*\). The above conclusion can be seen as follows: When \(\mathbf X \ne \mathbf X ^*\), if \(\mathbf A \mathbf X =\mathbf Y \), then \(\varPhi (\mathbf X ) > \varPhi (\mathbf X ^*)\) holds immediately due to the uniqueness of the solution of (2); otherwise, \(\Vert \mathbf{AX-Y }\Vert _F^2 > 0 = \Vert \mathbf A \mathbf X ^*-\mathbf Y \Vert _F^2\) and therefore
The remainder of the proof can follows the same line as the one in Theorem 1. \(\square \)
Appendix 3: Subgradient of \(\Vert \mathbf X \Vert _{2,1} \)
For \(\Vert \mathbf X \Vert _{2,1} = \sum _{j=1}^n \Vert \mathbf X ^j \Vert _{2}\), the subgradient of \(\Vert \mathbf X \Vert _{2,1} \) is obtained as
where
Rights and permissions
About this article
Cite this article
Zou, J., Fu, Y., Zhang, Q. et al. Split Bregman algorithms for multiple measurement vector problem. Multidim Syst Sign Process 26, 207–224 (2015). https://doi.org/10.1007/s11045-013-0251-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11045-013-0251-6