求解稀疏分裂可行问题的一种投影算法
|
摘要
本文研究了稀疏分裂可行问题.通过将分裂可行问题转化为一个目标函数为凸函数的稀疏约束优化问题,设计一种梯度投影算法来求解此问题,获得了算法产生的点列可以收敛到稀疏分裂可行问题的一个解.用数值例子说明了算法的有效性.
In this paper, we study the solution of sparsity split feasibility problem. By transforming the sparsity split feasibility problem into an sparsity constraints optimization problem whose objective function is convex, we design a gradient projection algorithm for solving the problem, and get that this method can converge to a solution. The numerical example is given to prove the effectiveness of the algorithm.
In this paper, we study the solution of sparsity split feasibility problem. By transforming the sparsity split feasibility problem into an sparsity constraints optimization problem whose objective function is convex, we design a gradient projection algorithm for solving the problem, and get that this method can converge to a solution. The numerical example is given to prove the effectiveness of the algorithm.
引文
[1] Censor Y, Elfving T. A multiprojection algorithm using Bregman projection in a product space[J].Numer. Algor., 1994, 8:221-239.
[2] Byrne C. Iterative oblique projection onto convex subsets and the split feasibility problem[J]. Inv.Prob., 2002, 18:441-453.
[3] Byrne C. A unified treatment of some iterative algorithms in signal processing and image reconstruction[J]. Inv. Prob., 2004, 20:103-120.
[4] Yang Q Z. The relaxed CQ algorithm solving the split feasibility problem[J]. Inv. Prob., 2004, 20:1261-1266.
[5] Qu B, Xiu N. A note on the CQ algorithm for the split feasibility problem[J]. Inv. Prob., 2005, 21:1655-1665.
[6] Agarwal A, Negahban S, Wainwright M. Fast global convergence rates of gradient methods for high-dimensional statistical recovery[J]. Adv. Neural Inf. Proc., Syst., 2010, 23:37-45.
[7] Blumensath T. Compressed sensing with nonlinear observations and related nonlinear optimization problems[J]. IEEE Trans. Inf. Theory, 2013, 59:3466-3474.
[8] Jalali A, Johnson C C, Ravikumar P K. On learning discrete graphical models using greedy methods[J]. Adv. Neural Inf. Proc. Syst., 2011, 24:1935-1943.
[9] Tewari A, Ravikumar P K, Dhillon I S. Greedy algorithms for structurally constrained high dimensional problems[J]. Adv. Neural Inf. Proc. Syst., 2011, 24:882-890.
[10] Yuan X, Li P, Zhang T. Gradient hard thresholding pursuit for sparsity-constrained optimization[R].ICML, 2014:127-135.
[11] Bahmani S, Ra.j B, Boufounos P. Greedy sparsity-constrained optimization[J]. J. Mach. Learn. Res.,2013, 14:807-841.
[12] Candes E J, Tao T. Decoding by linear programming[J]. IEEE Trans. Inf. Theory, 2005, 51:4203-4215.
[13] Donoho D L. Compressed sensing[J]. IEEE Trans. Inf. Theory, 2006, 52:1289-1306.
[14] Beck A, Eldar Y. Sparsity constrained nonlinear optimization:optimality conditions and algorithms[J]. SIAM J. Optim., 2013, 23:1480-1509.
[15] Pan L L, Xiu N H, Zhou S L. Gradient support projection algorithm for affine feasibilityproblem with sparsity and nonnegativity[J]. Math., 2014, 42:1439-1444.
[16] Bertsekas D P. Nonlinear programming(2nd ed.)[M]. Belmont, MA:Athena Scientific, 1999.
[2] Byrne C. Iterative oblique projection onto convex subsets and the split feasibility problem[J]. Inv.Prob., 2002, 18:441-453.
[3] Byrne C. A unified treatment of some iterative algorithms in signal processing and image reconstruction[J]. Inv. Prob., 2004, 20:103-120.
[4] Yang Q Z. The relaxed CQ algorithm solving the split feasibility problem[J]. Inv. Prob., 2004, 20:1261-1266.
[5] Qu B, Xiu N. A note on the CQ algorithm for the split feasibility problem[J]. Inv. Prob., 2005, 21:1655-1665.
[6] Agarwal A, Negahban S, Wainwright M. Fast global convergence rates of gradient methods for high-dimensional statistical recovery[J]. Adv. Neural Inf. Proc., Syst., 2010, 23:37-45.
[7] Blumensath T. Compressed sensing with nonlinear observations and related nonlinear optimization problems[J]. IEEE Trans. Inf. Theory, 2013, 59:3466-3474.
[8] Jalali A, Johnson C C, Ravikumar P K. On learning discrete graphical models using greedy methods[J]. Adv. Neural Inf. Proc. Syst., 2011, 24:1935-1943.
[9] Tewari A, Ravikumar P K, Dhillon I S. Greedy algorithms for structurally constrained high dimensional problems[J]. Adv. Neural Inf. Proc. Syst., 2011, 24:882-890.
[10] Yuan X, Li P, Zhang T. Gradient hard thresholding pursuit for sparsity-constrained optimization[R].ICML, 2014:127-135.
[11] Bahmani S, Ra.j B, Boufounos P. Greedy sparsity-constrained optimization[J]. J. Mach. Learn. Res.,2013, 14:807-841.
[12] Candes E J, Tao T. Decoding by linear programming[J]. IEEE Trans. Inf. Theory, 2005, 51:4203-4215.
[13] Donoho D L. Compressed sensing[J]. IEEE Trans. Inf. Theory, 2006, 52:1289-1306.
[14] Beck A, Eldar Y. Sparsity constrained nonlinear optimization:optimality conditions and algorithms[J]. SIAM J. Optim., 2013, 23:1480-1509.
[15] Pan L L, Xiu N H, Zhou S L. Gradient support projection algorithm for affine feasibilityproblem with sparsity and nonnegativity[J]. Math., 2014, 42:1439-1444.
[16] Bertsekas D P. Nonlinear programming(2nd ed.)[M]. Belmont, MA:Athena Scientific, 1999.