应用数学学报
首页  |  期刊介绍  |  编 委 会  |  投稿指南  |  期刊订阅  |  广告服务  |  相关链接  |  下载中心  |  联系我们  |  留言板
 
应用数学学报 英文版  
   
   
高级检索 »  
应用数学学报  2013, Vol. 36 Issue (4): 619-630    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索  |   
半定矩阵秩极小的非凸精确松弛
秦林霞, 修乃华, 孔令臣
北京交通大学应用数学系, 北京, 100044
A Nonconvex Exact Relaxation of the Semidefinite Matrix Rank Minimization
QIN Linxia, XIU Naihua, KONG Lingchen
Department of Applied Mathematics, Beijing Jiaotong University, Beijing, 10004
 全文: PDF (381 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 本文主要研究半定矩阵秩极小问题(P) 的非凸精确松弛及其性质. 首先, 为求解问题(P), 我们引入 其Schatten p-范数(0<p<1) 松弛, 记为(Sp). 其次, 通过定义半定限制等距常数和半定限制正交常数, 我们给出了问题(P)有 唯一解的充分条件. 最后, 利用半定限制等距性质, 我们给出了问题(P)和(Sp) 有相同唯一解的充分条件. 特别地, 对任意0<p<1, 我们还得到一个一致的精确恢复条件.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
秦林霞
修乃华
孔令臣
关键词半定矩阵秩极小问题   Schatten p-范数松弛   半定限制等距性质   精确恢复条件     
Abstract: In this paper, we emphasize on the nonconvex relaxation of the semidefinite matrix rank minimization problem and the involved properties. Firstly, we apply a nonconvex relaxation, the Schatten p-norm (0<p<1) semidefinite program, for solving the desired rank minimization problem. Next, by defining the semidefinite restricted isometry/orthogonal constant, we propose a sufficient condition for the uniqueness of the solution to (P). Finally, with the semidefinite restricted isometry property (semi-RIP), we give a sufficient condition under which the Schatten p-norm relaxation and the underlying matrix rank minimization share the unique common solution. In particular, for any 0<p<1, we obtain a uniform exact recovery condition.
Key wordssemidefinite matrix rank minimization   Scatten p-norm relaxation   semidefinite restricted isometry property   exact recovery condition   
收稿日期: 2013-03-25;
基金资助:国家基础研究计划(2010CB732501);国家自然科学基金(11171018);中央高校基本科研业务费(2013JBM095)资助项目
引用本文:   
秦林霞,修乃华,孔令臣. 半定矩阵秩极小的非凸精确松弛[J]. 应用数学学报, 2013, 36(4): 619-630.
QIN Linxia,XIU Naihua,KONG Lingchen. A Nonconvex Exact Relaxation of the Semidefinite Matrix Rank Minimization[J]. Acta Mathematicae Applicatae Sinica, 2013, 36(4): 619-630.
 
[1] Candés E J, Eldar Y, Strohmer T, Voroninski V. Phase Retrieval via Matrix Completion. SIAM J. Imaging Sci., 2013, 6(1): 199-225
[2] Candés E J, Strohmer T, Voroninski V. Phase Lift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming. Comm. Pure Appl. Math., 2012
[3] Flammia S T, Liu Y K. Direct Fidelity Estimation from Few Pauli Measurements. Phys. Rev. Lett., 2011, 106(23): 230501
[4] Gross D, Liu Y K, Flammia S T, Becker S, Eisert J. Quantum State Tomography via Compressed Sensing. Phys. Rev. Lett., 2010, 105: 150401
[5] Ji S, Sze K-F, Zhou Z, So A M-C, Ye Y. Beyond Convex Relaxation: a Polynomial-time Non-convex Optimization Approach to Network Localization. To appear in IEEE INFOCOM 2013, 2013
[6] Wang M, Xu W, Tang A. A Unique "Nonnegative" Solution to an Underdetermined Systems: from Vector to Matrices. IEEE Trans. Signal Process., 2011, 59(3): 1007-1016
[7] Chartrand R. Exact Reconstructions of Sparse Signals via Nonconvex Minimization. IEEE Signal Proc. Let., 2007, 14: 707-710
[8] Chartrand R. Fast Algorithms for Nonconvex Compressive Sensing: MRI Reconstruction from Very Few Data. IEEE International Symposium on Biomedical Imaging (ISBI), 2009
[9] Chartrand R, Staneva V. Restricted Isometry Properties and Nonconvex Compressive Sensing. Inverse Probl., 2008, 24: 1-14
[10] Chen X, Xu F, Ye Y. Lower Bound Theory of Nonzero Entries in Solutions of l2-lp Minimization. SIAM J. Scientific Computing, 2010, 32: 2832-2852
[11] Ge D, Jiang X, Ye Y. A Note on Complexity of l_p Minimization. Math. Program, 2011, 129: 285-299
[12] Majumdar A, Ward R.K. An Algorithm for Sparse MRI Reconstruction by Schatten p-norm (0Magn. Reson. Imaging, 2011, 29: 408-417
[13] Xu Z. Data Modeling: Visual Psychology Approach and L1/2 Regularization Theory. Proceedings of International Congress of Mathematicians, Section. Vol. 18, 2010
[14] Xu Z, Chang X, Xu F, Zhang H. L1/2 Regularization: a Thresholding Representation Theory and a Fast Solver. IEEE Trans. Neural Networks and Learning Systems, 2012, 23: 1013-1027
[15] Xu Z, Guo H, Wang Y, Zhang H. The Representative of L1/2 Regularization Among Lq (0Acta Automatica Sinica, 2012, 38(7): 1225-1228
[16] Candés E J, Tao T. Decoding by Linear Programming. IEEE Trans. Inform. Theory, 2004, 51: 4203-4215
[17] Cai T, Wang L, Xu G. New Bounds for Restricted Isometry Constants. IEEE Trans. Inform. Theory, 2010, 56(9): 4388-4394
[18] Hsia Y, Sheu R. On RIC Bounds of Compressed Sensing Matrices for Approximating Sparse Solutions Using l_q Quasi Norms. http://www.opti mization-online.org/DB_HTML/2012/09/3610.html, 2012
[19] Kong L, Xiu N. Exact Low-rank Matrix Recovery via Nonconvex Schatten p-minimization. Asia-Pac. J. Oper. Res., 2013, 30 (3), DOI: 10.1142/S0217595913400101
[20] Mo G, Li S. New Bounds on the Restricted Isometry Constant δ2k. Appl. Comput. Harmon. Anal., 2011, 31(3): 460-468
[21] Recht B, Fazel M, Parrilo P. Guaranteed Minimum Rank Solutions of Matrix Equations via Nuclear Norm Minimization. SIAM Review, 2010, 52: 471-501
[22] Zhang M, Huang Z, Zhang Y. Restricted p-isometry Properties of Nonconvex Matrix Recovery. IEEE Trans. Inform. Theory, 2013, DOI: 10.1109/TIT.2013.2250577
[23] Horn R A, Johnson C R. Topics in Matrix Analysis. Cambridge: Cambridge University Press, 1991
没有找到本文相关文献
  版权所有 © 2009 应用数学学报编辑部   E-mail: amas@amt.ac.cn
京ICP备05002806号-9