Concave minimization for sparse solutions of absolute value equations

Abstract

Based on concave function, the problem of finding the sparse solution of absolute value equations is relaxed to a concave programming, and its corresponding algorithm is proposed, whose main part is solving a series of linear programming. It is proved that a sparse solution can be found under the assumption that the connected matrixes have range space property(RSP). Numerical experiments are also conducted to verify the efficiency of the proposed algorithm.

Keywords

absolute value equations / concave minimization / sparsity / linear programming / range space property

References

[1] Mangasarian O L, Meyer R R. Absolute value equations [J]. Linear Algebra and Its Applications, 2006, 419(2/3): 359-367.

[2] Mangasarian O L. Absolute value programming [J]. Computational Optimization and Applications, 2007, 36(1): 43-53.

[3] Mangasarian O L. Absolute value equation solution via concave minimization[J]. Optimization Letters, 2007, 1(1): 3-8.

[4] Prokopyev O. On equivalent reformulations for absolute value equations [J]. Computational Optimization and Applications, 2009, 44(3): 363-372.

[5] Rohn J. A theorem of the alternatives for the equations AX ? B x ? b [J]. Linear Multilinear Algebra, 2004, 52(6): 421-426.

[6] Mangasarian O L. A generalized Newton method for absolute value equations [J]. Optimization Letters, 2009, 3(1): 101-108.

[7] Hu S L, Huang Z H. A note on absolute value equations [J]. Optimization Letters, 2010, 4(3): 417-424.

[8] Zhang M, Huang Z H, Li Y F. The sparsest solution to the system of absolute value equations [J]. Journal of the Operations Research Society of China, 2015, 3(1): 31-51.

[9] Candès E J, Romberg J K, Tao T. Stable signal recovery from incomplete and inaccurate measurements [J]. Communications on Pure and Applied Mathematics, 2006, 59(8): 1207-1223.

[10] Candès E J, Romberg J, Tao T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information [J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509.

[11] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[12] Donoho D L, Elad M. Optimality sparse representation in general (nonorthogonal) dictionaries via l1 minimization [J]. Proceedings of the National Academy of Sciences of the United States of America, 2003, 100(5): 2197-2202.

[13] Donoho D L, Huo X. Uncertainty principles and ideal atomic decomposition [J]. IEEE Transactions on Information Theory, 2001, 47(7): 2845-2862.

[14] Gribonval R, Nielsen M. Sparse decompositions in unions of bases [J]. IEEE Transactions on Information Theory, 2003, 49(12): 3320-3325.

[15] Zhang Y. Theory of compressive sensing via l1-minimization: A non-RIP analysis and extensions [J]. Journal of the Operations Research Society of China, 2013, 1(1): 79-105.

[16] Zhao Y B, Li D. Reweighted l1-minimization for sparse solutions to underdetermined linear systems [J]. SIAM Journal on Optimization, 2012, 22(3): 1065-1088.

[17] Zhou S L, Kong L C, Xiu N H. New bounds for RIC in compressed sensing [J]. Journal of the Operations Research Society of China, 2013, 1(2): 227-237.

[18] Luo Z Y, Qin L X, Kong L C, et al. The nonnegative zeronorm minimization under generalized Z-matrix measurement [J]. Journal of Optimization Theory and Applications, 2014, 160(3): 854-864.