|
非负稀疏优化的精确松弛理论研究
摘要
非负稀疏优化是指利用待恢复变量的稀疏性,寻找一个带有非负约束的欠定线性等式系统最稀疏的解.在向量空间,该问题实质上是非负l0极小问题；而在矩阵空间,该问题表现为半定秩极小问题.非负稀疏优化在DNA微阵列、量子成像、医学成像、光谱学、网络定位及隐马尔可夫模型等领域有广泛应用,并与反问题、主成分分析、组合优化、线性规划、半定规划等问题联系密切,近年来逐渐引起数学及众多应用领域专家的重视,成为一个热点研究课题.本文主要研究非负稀疏优化的解集性质及精确松弛条件.
第一章绪论部分.主要对非负稀疏优化问题的研究意义、数学模型做了简单介绍,并全面综述了非负稀疏优化松弛理论的研究现状. 第二章探讨了非负稀疏优化问题的解集特征.针对向量空间非负稀疏优化,首先借助零范数的不同取值,引入n维向量空间的特殊划分,并由此证明了该问题任意两个不同的最优解必有不同的支撑集,从而证得其最优解必然在其可行域的极点上达到.这为直接利用启发式算法求解此组合问题,或者寻找更多合适的松弛模型奠定了基础.针对矩阵空间非负稀疏优化,我们证明若其任意两个不同最优解的特征值分解中有相同的正交矩阵,则对应的特征值向量必有不同的支撑集. 第三章针对向量空间非负稀疏优化问题的凸松弛及非凸松弛,提出了广义Z-矩阵精确松弛条件.第一节通过引入广义Z-矩阵概念和最小元素理论,我们研究了特殊条件下非负稀疏优化问题的可行性.第二节我们证明如果测量矩阵是一个广义Z-矩阵且观测向量b非负,则向量空间非负稀疏优化问题与其线性松弛及lp(0 第五章是推广与展望部分.对称锥可以看作是非负向量锥和半定矩阵锥的推广,故而第一节我们给出关于对称锥上问题的一些研究结果.第二节通过深入分析非负稀疏优化的研究现状,我们列举了目前值得考虑的几个问题,这些问题有可能成为下一步工作的方向. The nonnegative sparse optimization is to find the sparsest solution of an underdeter-mined linear equation with the nonnegative constraints, making use of the sparsity of the variable under consideration. In the vector space, it is essentially the nonnegative l0norm minimization; while in the matrix space, it becomes the semidefinite matrix rank minimiza-tion. Owing to the wide applications in DNA microarrays, quantum state tomography, medical imaging, spectroscopy, sensor location and hidden Markov models together with the close connection with inverse problems,principal component analysis, combinatorial optimization, linear optimization and semidefinite optimization, the nonnegative sparse optimization has attracted much attention of both mathematicians and engineers in many application areas, and obtained rapid development in recent years. This thesis is mainly concerned with the solution property and the exact relaxation conditions. Chapter1briefly introduces the significance and mathematical models of nonnegative sparse optimization, and reviews the research status of the relaxation theory. In chapter2, we discuss the solution property of the nonnegative sparse optimiza-tion. For the nonnegative sparse optimization over vector space, we introduce the special partition for the space Rn in the light of the l0norm function, based on which we show that any two distinct solutions of the desired problem must have different support sets. hence we prove that any solution to the underlying problem must be one of the extreme points of the feasible set. This can lay the foundation for the heuristic algorithms or some new relaxations of the underlying combinatorial problem. For the nonnegative sparse op- timization over matrix space, we show that when the eigenvalue decomposition of any two different solutions share the same orthogonal matrix, the corresponding eigenvalue vectors can not share the same support set. In chapter3, we investigate the generalized Z-matrix exact relaxation condition for both the convex and nonconvex relaxations of the nonnegative sparse optimization over vector space. Firstly, by introducing the concept of generalized Z-matrix and least ele-ment theory, we investigate the feasibility of the nonnegative l0norm optimization under some conditions. Moreover, we show that if the observation vector is nonnegative and the measurement matrix is a generalized Z-matrix, the aforementioned problem and its linear/lp (0 In chapter5, some generalizations are studied and several future issues are discussed. Since the nonnegative orthant and the semidefinite matrix cone are special cases of the so-called symmetric cone, some useful properties of solution sets of symmetric cone opti-mization problems are explored in the first section. By reviewing the existing results on the nonnegative optimization, four possible research issues are pointed out which deserve future study.
引文
[1]L. Applebaum, S. D. Howard, S. Searle, R. Calderbank, Chirp sensing codes:deter-ministic compressed sensing measurements for fast recovery, Appl. Comput. Har-mon. Anal.,26 (2009),283-290.
[2]A.S. Bandeira, M. Fickus, D.G. Mixon, P. Wong, The road to deterministic matrices with the restricted isometry property, arXiv:1201.1234,2012. [3]A. Bandeira, K. Scheinberg, L.N. Vicente, On partially sparse recovery, Tech. Rep., Department of Mathematics, University of Coimbra,2011. [4]A. Beck, M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems algorithm, SI AM J. Imaging Sci.,2 (2009),183-202. [5]R. Berinde, A.C. Gilbert, P. Indyk, H. Karloff, M.J. Strauss, Combining geometry and combinatorics:a unified approach to sparse signal recovery, IEEE Allerton CCC, (2008),798-805. [6]A. Berman, R.J. Plemmons, Nonnegative matrices in the mathematical sciences, SIAM,1994. [7]R. Bhatia, Matrix analysis, Springer-Verlag, New York,1997. [8]J.F. Bonnans, A. Shapiro, Perturbation analysis of optimization problems, Springer-Verlag, New York,2000. [9]S. Boyd, L. Vandenberghe, Convex optimization, Cambridge university press, New York,2004. [10]A.M. Bruckstein, D.L. Donoho, M. Elad, Prom sparse solutions of systems of equa-tions to sparse modeling of signals and images, SIAM Rev.51 (2009),34-81. [11]A.M. Bruckstein, M. Elad, M. Zibulevsky, On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations, IEEE Trans. Inform. Theory, 54 (2008),4813-4820. [12]S. Burer, R. Monteiro, Local mimima and convergence in low-rank semidefinite pro-gramming, Math. Program. Ser. A,103 (2005),427-444. [13]J. Cai, E.J. Candes, Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optimiz.,20 (2010),1956-1982. [14]T. Cai, L. Wang, G. Xu, New bounds for restricted isometry constants, IEEE Trans. Inform. Theory,56 (2010),4388-4394. [15]T. Cai, L. Wang, G. Xu, Shifting inequality and recovery of sparse signals, IEEE Trans. Signal Process.,58 (2010),1300-1308. [16]T. Cai, A. Zhang, Sharp RIP bound for sparse signal and low-rank matrix recovery, Appl. Comput. Harmon. Anal.,35 (2013),74-93. [17]J.F. Cai, S. Osher, Z.W. Shen, Linearized Bregman iterations for compressed sensing, Math. Comp.78 (2009),1515-1536. [18]T. Cai, A. Zhang, Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, Tech. Rep., University of Pennsylvania,2013. [19]R. Calderbank, S. Howard, S. Jafarpour, A sublinear algorithm for sparse recon-struction with 12/12 recovery guarantees, IEEE CAMSAP, (2009),209-212. [20]R. Calderbank, S. Howard, S. Jafarpour, Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property, IEEE J. Sel. Top. Signal Process.,4 (2010),358-374. [21]E.J. Candes, Compressive sampling. Proc. International Congress of Mathematics, Madrid, Spain,3(2006),1433-1452. [22]E.J. Candes, The restricted isometry property and its implications for compressed sensing, Compte Rendus de I'Academie des Sciences. Paris, Prance, ser. I,346 (2008),589-592. [23]E.J. Candes, Y. Eldar, T. Strohmer, V. Voroninski, Phase retrieval via matrix com-pletion, SIAM J. Imaging Sci.,6 (2013),199-225. [24]E.J. Candes, Y. Plan, Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements, IEEE Trans. Inform. Theory,57 (2011),2342-2359. [25]E.J. Candes, P.A. Randall, Highly robust error correction by convex programming, IEEE Trans. Inform. Theory,54 (2008),2829-2840. [26]E.J. Candes, B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math.,9 (2009),717-772. [27]E.J. Candes, B. Recht, Simple bounds for recovering low-complexity models, Math. Program.,2012,1-13. [28]E.J. Candes, J. Romberg, Sparsity and incoherence in compressive sampling, Inverse Probl.,23 (2007),969-985. [29]E.J. Candes. J. Romberg, T. Tao, Stable signal recovery from incomplete and inac-curate measurements, Comm. Pure Appl. Math.,59 (2006),1207-1223. [30]E.J. Candes, J. Romberg, T. Tao, Robust uncertainty principles:Exact signal re-construction from highly incomplete frequency information, IEEE Trans. Inform. Theory,52 (2006),489-509. [31]E.J. Candes, M. Rudelson, T. Tao, R. Vershynin, Error correction via linear pro-gramming, IEEE FOCS,2005,295-308. [32]E.J. Candes, T. Strohmer, V. Voroninski, PhaseLift:exact and stable signal recovery from magnitude measurements via convex programming, Comm. Pure Appl. Math., 2012. [33]E.J. Candes, T. Tao, Decoding by linear programming. IEEE Trans. Inform. The-ory,51 (2005),4203-4215. [34]E.J. Candes. T. Tao, Near optimal signal recovery from random projections:Uni-versal encoding strategies? IEEE Trans. Inform. Theory,52 (2006),5406-5425. [35]E.J. Candes. T. Tao, The Dantzig selector:Statistical estimation when p is much larger than n (with discussion), Ann. Statist,35 (2007),2313-2351. [36]E.J. Candes, M.B. Wakin, An introduction to compressive sampling, IEEE Signal Proc. Mag.,21 (2008),21-30. [37]E.J. Candes, M.B. Wakin, S. Boyd, Enhancing sparsity by reweighted l1 minimiza-tion, J. Fourier Anal. Appl,14 (2008),877-905. [38]V. Chandrasekaran, B. Recht, P.A. Parrilo, A.S. Willsky, The convex geometry of linear inverse problems, IEEE Allerton CCC,2011. [39]V. Chandrasekaran, S. Sanghavi, P.A. Parrilo, A.S. Willsky, Rank-sparsity incoher-ence for matrix decomposition, SIAM J. Optimiz.,21 (2011),572-596. [40]R. Chartrand, Exact reconstructions of sparse signals via nonconvex minimization, IEEE Signal Proc. Let.,14 (2007),707-710. [41]R. Chartrand, Fast algorithms for nonconvex compressive sensing:MRI reconstruc-tion from very few data, IEEE ISBI,2009. [42]R. Chartrand, V. Staneva, Restricted isometry properties and nonconvex compres-sive sensing, Inverse Probl.,24 (2008),1-14. [43]R. Chartrand, W. Yin, Iteratively reweighted algorithms for compressive sensing, IEEE ICASSP,(2008),3869-3872. [44]J.S. Chen, S. Pan, A survey on SOC complementarity functions and solution methods for SOCPs and SOCCPs, Pacific J. Optim.,8 (2012),33-74. [45]S. Chen, D.L. Donoho, M. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput.,20 (1998),33-61. [46]X. Chen, D. Ge, Z. Wang, Y. Ye, Complexity of unconstrained l2-lp minimization, Math. Program., to appear,2013. [47]X. Chen, M. Ng, C. Zhang, Non-Lipschitz lp-regularization and box constrained model for image restoration, IEEE Trans. Image Process.,21 (2012),4709-4721. [48]X. Chen, F. Xu, Y. Ye, Lower bound theory of nonzero entries in solutions of l2-lp minimization,SIAM J. Sci. Comput.,32 (2010),2832-2852. [49]X. Chen, W. Zhou, Convergence of the reweighted l1 minimization algorithm for l2-lp minimization, Comput. Optim. Appl, DOI:10.1007/s10589-013-9553-8,2013. [50]Y. Chen, N. Xiu, D.T. Peng, Global solution of non-Lipschitz S2-Sp minimization over the positive semidefinite cones, Optim. Lett.,2013. [51]G. Chinn,P.D. Olcott, C.S. Levin, Sparse Signal Recovery Methods for Multiplexing PET Detector Readout, IEEE Trans. Med. Imag.,32 (2013),932-942. [52]A. Cohen, W. Dahmen, R. DeVore. Compressed sensing and best k-term approxi-mation, J. Amer. Math. Soc.,22 (2009),211-231. [53]R. W. Cottle, S.M. Guu, Two characterizations of sufficient matrices, Linear Algebra Appl.,170 (1992),65-74. [54]R.W. Cottle, J.-S. Pang, R.E. Stone, The linear complementarity problem. Academic Press, Boston,1992. [55]R.W. Cottle, J.-S. Pang, V. Venkateswaran, Sufficient matrices and the linear com-plementarity problem, Linear Algebra Appl.,114/115 (1989),231-249. [56]J. Dattorro, Convex optimization and Euclidean distance geometry, Meboo Publish-ing USA, California,2005. [57]M. Davenport, M. Duarte, Y. Eldar, G. Kutyniok, Compressed sensing:theory and applications, Cambridge University Press,2012. [58]M.E. Davies, R. Gribonval, Restricted isometry constants where lp sparse recovery can fail for 0< p<1, IEEE Trans. Inform. Theory,55 (2009),2203-2214. [59]R.A. DeVore, Deterministic constructions of compressed sensing matrices, Journal of Complexity,28 (2007),918-925. [60]A. Divekar, O. Ersoy, Theory and applications of compressive sensing, Tech. Rep., Electrical and Computer Engineering, Purdue University,2010. [61]K. Do Ba. P. Indyk, E. Price, D. Woodruff, Lower bounds for sparse recovery, Proc. SODA,2010. [62]D.L. Donoho, Neighborly polytopes and sparse solutions of underdetermined linear equations, Manuscript, Department of Statistics, Stanford University,2005. [63]D.L. Donoho, For most large underdetermined systems of linear equations the min-imal li norm solution is also the sparsest solution, Comm. Pure Appl.Math.,59 (2006),797-829. [64]D.L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory,52 (2006),1289-1306. [65]D.L. Donoho, High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension, Discrete and Comput. Geometry,35 (4),617-652,2006. [66]D.L. Donoho, M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via h minimization, Proc. Natl. Acad. Sci., USA,100 (2003),2197-2202. [67]D.L. Donoho, X. Huo, Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inform. Theory,47 (2001),2845-2862. [68]D.L. Donoho, P.B. Starck, Uncertainty principles and signal recovery, SIAM J. Appl. Math.,49 (1989),906-931. [69]D.L. Donoho, J. Tanner, Sparse nonnegative solutions of underdetermined linear equations by linear programming, Proc. Natl. ACAD. Scl., USA,102 (2005),9446-9451. [70]D.L. Donoho, J. Tanner, Neighborliness of Randomly-Projected Simplices in High Dimensions, Proc. Natl. ACAD. Scl., USA,102 (2005),9452-9457. [71]D.L. Donoho, J. Tanner, Counting faces of randomly-projected polytopes when the projection radically lowers dimension, Journal of the AMS,22 (2009),1-53. [72]D.L. Donoho, J. Tanner, Counting the faces of randomly-projected hypercubes and orthants with applications, Discr. Comput. Geom.,43 (2008),522-541. [73]D.L. Donoho, J. Tanner, Precise undersampling theorems, Proc. IEEE,98 (2010), 913-924. [74]M.F. Duarte, Y. Eldar, Structured compressed sensing:Theory and applications, IEEE Trans. Signal Process.,2011. [75]K. Dvijotham, M. Fazel, A nullspace analysis of the nuclear norm heuristic for rank minimization, IEEE ICASSP,2010. [76]M. Elad, A.M. Bruckstein, A generalized uncertainty principle and sparse represen-tation in pairs of bases, IEEE Trans. Inform. Theory,48 (2002),2558-2567. [77]Y.C. Eldar, D. Needell, Y. Plan, Uniqueness conditions for low-rank matrix recovery, Appl. Comput. Harmon. Anal,33 (2012),309-314. [78]F. Facchinei, J.-S. Pang, Finite-dimensional variational inequalities and comlemen-tarity problems, Springer-Verlag, New York,2003. [79]J. Faraut, A. Korriyi, Analysis on Symmetric Cones, Oxford University Press, Ox-ford,1994. [80]M. Fazel, H. Hindi, S. Boyd, A rank minimization heuristic with application to minimum order system approximation, Proc. American Control Conference,2001. [81]M. Fiedler, V. Ptak, On matrices with non-positive Off-diagonal elements and pos-itive principle minors, Czechoslov. Math. J.,12 (1962),382-400. [82]S.T. Flammia, Y.-K. Liu, Direct fidelity estimation from few Pauli measurements, Phys. Rev. Lett.,106 (2011),230501. [83]M. Fornasier, H. Rauhut, R. Ward, Low-rank matrix recovery via iteratively reweighted least squares minimization, SIAM J. Optimiz.21 (2011),1614-1640. [84]S. Foucart, A note on guaranteed sparse recovery vi lq-minimization, Appl. Comput. Harmon. Anal,29 (2010),97-103. [85]S. Foucart, M. Lai, Sparsest solutions of underdetermined linear systems via lq-minimization for 0< q< 1, Appl. Comput. Harmon. Anal.,26 (2009),395-407. [86]G. Fung, O. Mangasarian, Equivalence of minimal l0-and lp-norm solutions of lin-ear equalities, inequalities and linear programs for sufficiently small p, J. Optimiz. Theory App.,151 (2011),1-10. [87]Y. Gao, D. Sun, A majorized penalty approach for calibrating rank constrained correlation matrix problems, http:www.math. nus.edu.sg/matsundef/MajorPen.pdf, 2010. [88]G. Gasso, A. Rakotomamonjy, S. Canu, Recovering sparse signals with a certain family of noncovex penalties and DC programming, IEEE Trans. Signal Process., 57 (2009),4686-4698. [89]D. Ge, X. Jiang, Y. Ye, A note on complexity of lp minimization, Math. Program., 129 (2011),285-299. [90]M.S. Gowda, On the extended linear complementarity problem, Math. Program.,72 (1996),33-50. [91]M.S. Gowda, Y. Song, On semidefinite linear complementarity problems, Math. Pro-gram., Ser. A,88 (2000),575-587. [92]M.S. Gowda, R. Sznajder, Automorphism invariance of P and GUS properties of linear transformations on Euclidean Jordan algebras, Math. Oper. Res.,31 (2006), 109-123. [93]M.S. Gowda, R. Sznajder, The Q-property of composite transformations and the P-property of Stein-type transformationis on self-dual and symmetric cones, Linear Algebra Appl.416 (2006),437-451. [94]M.S. Gowda, R. Sznajder, Some global uniqueness and solvability results for linear complementarity problems over symmetric cones, SI AM J. Optimiz,18 (2007),461-481. [95]M.S. Gowda, R. Sznajder, J. Tao, Some P-properties for linear transformations on Euclidean Jordan algebras, Linear Algebra Appl,393 (2004),203-232. [96]M.S. Gowda,J. Tao, Z-tansformations on proper and symmetric cones, Math. Pro-gram., DOI:10.1007/s10107-007-0159-8. [97]D. Gross, Y.-K. Liu, S.T. Flammia, S. Becker, J. Eisert, Quantum state tomography via compressed sensing, Phys. Rev. Lett.,105 (2010),150401. [98]S.M. Guu, R.W. Cottle, On a subclass of Po, Linear Algebra Appl,223/224 (1995), 325-335. [99]E.T. Hale, W. Yin, Y. Zhang. A fixed-point continuation method for l1-minimization: methodology and convergence. SIAM J. Optimiz.,19(2008),1107-1130. [100]韩继业,修乃华,戚厚铎,非线性互补理论与算法,上海科学技术出版社,上海,2006. [101]Z.T. Harmany, R.F. Marcia, R.M. Willett, Spiral out of convexity:Sparsity-regularized algorithms for photon-limited imaging, Computational Imaging VIII, C. A.Bouman et al., Eds., San Jose, CA,7533 of Proc. SPIE-IS& T Electron. Imaging,2010. [102]R.A. Horn, C.R. Johnson, Topics in matrix analysis, Cambridge University Press, Cambridge,1991. [103]Y. Hsia, R. Sheu, On RIC bounds of compressed sensing matrices for approximating sparse solutions using lq quasi norms, http://www.optimization-online.org/DBH TML/2012/09/3610. html. [104]B. Huang, S.Q. Ma, D. Goldfarb, Accelerated linearized Bregman method, J. Sci. Comput.,54(2013),428-453. [105]http://dsp.rice.edu/cs. [106]S. Ji, K.-F. Sze, Z. Zhou, A.M.-C. So, Y. Ye, Beyond convex relaxation:A polynomial-time non-convex optimization approach to network localization, To appear in IEEE INFOCOM 2013,2013. [107]A. Juditsky, F.K. Karzan, A. Nemirovski, Verifiable conditions of l1 recovery for sparse signals with sign restrictions, Math. Program. Ser. B,127 (2011),89-122. [108]A. Juditsky,A. Nemirovski.On verifiable sufficient conditions for sparse signal re-covery via l1 minimization, Math. Program.,127 (2011),57-88. [109]M.A. Khajehnejad, A.G. Dimakis, W. Xu, B. Hassibi, Sparse recovery of nonnegative signals with minimal expansion, IEEE Trans. Signal Process.,59 (2011),196-208. [110]L. Kong, N. Xiu, Exact low-rank matrix recovery via nonconvex Schatten p-minimization, Asia-Pac. J. Oper. Res.,30 (2013), DOI:10.1142/S0217595913400101. [111]L. Kong, J. Sun, J. Tao, N. Xiu, Sparse recovery on Euclidean Jordan algebras, Submitted,2013. [112]L. Kong, J. Sun, N. Xiu, S-semigoodness for low-Rank semidefinite matrix recovery, to appear in Pacific J. Optim.,2013. [113]L. Kong, L. Tuncel, N. Xiu, S-goodness for low-rank matrix recovery, Abstr. Appl. Anal, Vol.2013 (2013), Article ID 101974,9 pages. [114]M. Kojima,N. Megiddo. T. Noma, Yoshise, A., A unified approach to interior point algorithms for linear complementarity problems, Springer-Verlag, Berlin,1991. [115]F. Krahmer, R. Ward, New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property, SIAM J. Math. Anal.,43,2010. [116]A. Krol, S. Li, L. Shen, Y. Xu, Preconditioned alternating projection algorithms for maximum a Posteriori ECT Reconstruction, Inverse Probl.,28 (2012),115005, DOI:10.1088/0266-5611/28/11/115005. [117]M.J. Lai, S. Li, L. Y. Liu, H. Wang, Two results on the Schatten p-quasi-norm minimization for low-rank matrix recovery, Tech. Rep.,2012. [118]M.J. Lai and L.Y. Liu, A new estimate of restricted isometry constants for sparse solutions, Appl. Comput. Harmon. Anal,30 (2011),402-406. [119]K. Lee, Y. Bresler. Admira, Atomic decomposition for minimum rank approxima-tion, IEEE Trans. Inform. Theory,56 (2010),4402-4416. [120]Q. Li, Nearest low-rank correlation matrix problem, Doctoral thesis, Hunan Univer-sity,2010. [121]S. Li, F. Gao, G. Ge, S. Zhang, Deterministic construction of compressed sensing matrices via algebraic curves, IEEE Trans. Inform. Theory,58 (2012),5035-5041. [122]Y. Liu, Y. Dai, Z. Luo, Joint power and admission control via linear programming deflation, IEEE Trans. Signal Process.,61 (2013),1327-1338. [123]Z. Liu, L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification, SIAM J. Matrix Anal. Appl,31 (2009), 1235-1256. [124]M.S. Lobo, L. Vandenberghe, S. Boyd, H. Lebret, Applications of seconde-order cone programming, Linear Algebra Appl,284 (1998),193-228. [125]Y. Lu, L. Zhang, J. Wu, A smoothing majorization method for l2-lp matrix mini-mization, optimization-online.org,2013. [126]Z. Lu, T. Pong, Interior point methods for computing optimal designs, Optimization-online.org,2010. [127]Z. Luo, L. Kong, N. Xiu, Minimum rank Lyapunov solutions in Euclidean Jordan algebra, Tech. Rep., Beijing Jiaotong University,2012. [128]Z. Luo, L. Qin, L. Kong, N. Xiu, The nonnegative lq norm minimization under generalized Z-matrix measurement, J. Optimiz. Theory App., DOI:10.1007/s 10957-013-0325-5,2013. [129]Z. Luo, J. Tao, N. Xiu, Lowest-rank solutions of continuous and discrete Lyapunov equations over symmetric cone, IEEE Trans. Auto. Control,2013. [130]Z. Luo, N. Xiu, Exact relaxations for two special semidefinite matrix rank mini-mization problem, Tech. Rep., Beijing Jiaotong University,2013. [131]S. Ma, D. Goldfarb, L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program. Ser. A,128 (2011),321-353. [132]M. Mesbahi, G. P. Papavassilopoulos, On the rank minimization problem over a positive semidefinite linear matrix inequality, IEEE Trans. Auto. Control,42 (1997), 239-243. [133]G. Mo, S. Li, New bounds on the restricted isometry constant 62k, Appl. Comput. Harmon. Anal,31 (2011),460-468. [134]K. Mohan, M. Fazel, New restricted isometry results for noisy low-rank recovery, ISIT, Austin,2010. [135]K. Mohan, M. Fazel, Iterative reweighted algorithms for matrix rank minimization, J. Mach. Learn. Res.,13 (2012),3441-3473. [136]B.K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput., 24 (1995),227-234. [137]D. Needell, J.A. Tropp, Cosamp:Iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal,26 (2009),301-321. [138]S. Oymak, M.A. Khajehnejad, B. Hassibi, Improved Thresholds for Rank Minimiza-tion, IEEE ICASSP, (2011),5988-5991. [139]S. Oymak, B. Hassibi, New null space results and recovery thresholds for matrix rank minimization, arXiv:1011.6326,2010. [140]S. Oymak, K. Mohan, M. Fazel. B. Hassibi, A simplified approach to recovery con-ditions for low rank matrices, arXiv:1103.1178,2011. [141]D. Peng, N. Xiu, J. Yu, S1/2 regularization and fixed point algorithm for low-rank matrix recovery, Tech. Rep., Beijing Jiaotong University,2013. [142]L. Qin, L. Kong, J. Han, Sufficiency of linear transformations on Euclidean Jordan algebras, Optim. Lett.,3 (2009),265-276. [143]L. Qin, N. Xiu, L. Kong, Y. Li, Linear program relaxation of sparse nonnegative recovery in compressive sensing microarrays, Comput. Math. Methods Med., Vol. 2012 (2012), Article ID 646045,8 pages. [144]秦林霞,修乃华,孔令臣,半定矩阵秩极小的非凸精确松弛,应用数学学报,36(2013),619-630. [145]H. Rauhut, Compressive sensing and structured random matrices, Radon Series Comp. Appl. Math.,9 (2010),1-92. [146]H. Rauhut, J. Romberg, J.A. Tropp, Restricted isometries for partial random circu-lant matrices, Appl. Comput. Harmon. Anal,32 (2012),242-254. [147]B. Recht, M. Fazel, P. Parrilo, Guaranteed minimum rank solutions of matrix equa-tions via nuclear norm minimization, SIAM Rev.,52 (2010),471-501. [148]B. Recht. W. Xu. B. Hassibi. Necessary and sufficient conditions for success of the nuclear norm heuristic for rank minimization, Proc. IEEE CDC, Mexico,2008. [149]B. Recht, W. Xu, B. Hassibi, Null space conditions and threshlods for rank mini-mization, Math. Program. B,127 (2011),175-202. [150]R.T. Rockafellar, Convex analysis. Princeton, New Jersey,1970. [151]R.T. Rockafellar, R.J-B Wets, Variational analysis, Springer-Verlag, Berlin, Heidel-berg,1998. [152]M. Rudelson, R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements, Comm. Pure Appl. Math.,61 (2008),1025-1045. [153]R. Schneider, Recent Results on Random Polytopes, Boll. Unione Mat. Ital,9 (2008),17-39. [154]Y. Sharon, J. Wright, Y. Ma, Computation and relaxation of conditions for equiv-alence between l1 and l0 minimization, submitted to IEEE Trans. Inform. Theory, 2007. [155]M.A. Sheikh, S. Sarvotham, O. Milenkovic, R.G. Baraniuk, DNA array decoding from nonlinear measurements by belief propagation, Proc.14-th IEEE Workshop on Statistical Signal, Washington D. C., USA,2007,215-219. [156]Y. Shen, S. Li, Restricted p-isometry property and its application for nonconvex compressive sensing, Adv. Comput. Math.,37 (2012),441-452. [157]D.C. Song, Z.X. Feng, Properties of generalized Z-matrices and M-matrices, J. Fushun Petroleum Institute,23 (2003),78-80. [158]T. Strohmer, R.W. Heath, Grassmannian frames with applications to codting and communication, Appl. Comput. Harmon. Anal,14 (2004),257-275. [159]D.F. Sun., The low-rank correlation matrix problems:nonconvex regularization and successive convex relaxations. BJTU talk,2012. [160]S. Theodoridis, Y. Kopsinis, K. Slavakis, Sparsity-aware learning and compressed sensing:an overview, arXiv:1211.5231,2012. [161]M.J. Todd, Semidefinite optimization, Acta Numerica,10 (2001),515-560. [162]K.C. Toh, S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pacific J. Optim.6(2010),615-640. [163]J.A. Tropp. Greed is good:Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory,50 (2004),2231-2242. [164]L. Tuncel, Y. Wang, N. Xiu. a penalty method based on differece of two norms for sparse reconstruction, Tech. Rep, University of Waterloo,2013. [165]H. Valiaho. Criteria for sufficient matrices. Linear Algebra Appl,233 (1996),109-129. [166]H. Valiaho, P*-matrices are just sufficient, Linear Algebra Appl,239 (1996),103-108. [167]王宜举,修乃华,非线性规划理论与算法,陕西科学技术出版社,西安,2004. [168]M. Wang, W. Xu, A. Tang, A unique "nonnegative" solution to an underdetermined systems:from vector to matrices, IEEE Trans. Signal Process.,59 (2011),1007-1016. [169]H. Wang, S. Li, The bounds of restricted isometry constants for low rank matrices recovery, Sci. China Ser. A, in press,2013. [170]文再文,印卧涛,刘歆,张寅,压缩感知和稀疏优化简介,运筹学学报,16(2012),49-63. [171]Z. Wen, W. Yin, Y. Zhang, Solving a low-rank factorization model for matrix com-pletion by a nonlinear successive over-relaxation algorithm, Tech. Rep. TR10-07, Rice University,2010. [172]H. Wolkowicz, R. Saigal, L. Vandenberghe, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, Kluwer Academic Publishers, Boston,2000. [173]修乃华,韩继业,对称锥互补问题,数学进展,1(2007),3-14. [174]W. Xu, B. Hassibi, Compressive sensing over the Grassmann manifold:a unified geometric framework, arXiv:1005.3729,2010. [175]许志强,压缩感知,中国科学,42(2012),865-877. [176]Z. Xu, X. Chang, F, Xu, H, Zhang, L1/2 Regularization:A thresholding representation theory and a fast solver, IEEE Trans. Neural Networks and Learning Systems,23 (2012),1013-1027. [177]Z. Xu, H. Guo, Y. Wang, H. Zhang, The representative of L1/2regularization among Lq(0 [179]J. Yang, Y. Zhang, Alternating direction algorithms for l1-problems in compressive sensing, SIAM J. Sci. Comput.,33 (2011),250-278. [180]W. Yin, S. Osher, D. Goldfarb, J. Darbon, Bregman iterative algorithms for l1 minimization with applications to compressed sensing, SIAM J. Imaging Sci.,1 (2008),143-168. [181]N.Y. Yu, Deterministic compressed sensing matrices from additive character se-quences, arXiv.1010.0011,2010. [182]M.C.Yue, A.M. So, A perturbation inequality for the Schatten-p quasi-norm and its applications to low-rank matrix recovery, arXiv:1209.0377,2012. [183]M. Zhang, Z. Huang, Y. Zhang, Restricted p-isometry properties of nonconvex matrix recovery, IEEE Trans. Inform. Theory, DOI:10.1109/TIT.2013.2250577,2013. [184]Y. Zhang. A Simple Proof for Recoverability of l1-Minimization:Go Over or Under? Tech. Rep. TR05-09, Rice University,2005. [185]Y. Zhang, A simple proof for the recoverability of l1-minimization (II):the nonneg-ative case, Tech. Rep. TR05-10, Rice University,2005. [186]Y. Zhang, On Theory of Compressive Sensing via l1 Minimization:Simple Deriva-tions and Extensions, Tech. Rep. TR08-11, Rice University,2008. [187]Y. Zhang, A Non-RIP Theory for Compressive Sensing, Tech. Rep. TR05-10, Rice University,2012. [188]Y. Zhao, An approximation theory of matrix rank minimization and its application to quadratic equations, Linear Algebra Appl.,437 (2012),77-93. [189]S. Zhou, L. Kong, Z. Luo, N. Xiu, New RIC Bounds via lp-minimization with 0< q< 1 in Compressed Sensing, arxiv:1308.0455,2013. |