Orthogonal multi-matching pursuit（OMMP）is a natural extension of orthogonal matching pursuit（OMP）in the sense that N（N≥1）indices are selected per iteration instead of 1.In this paper,the theoretical performance...Orthogonal multi-matching pursuit（OMMP）is a natural extension of orthogonal matching pursuit（OMP）in the sense that N（N≥1）indices are selected per iteration instead of 1.In this paper,the theoretical performance of OMMP under the restricted isometry property（RIP）is presented.We demonstrate that OMMP can exactly recover any K-sparse signal from fewer observations y=φx,provided that the sampling matrixφsatisfiesδKN-N＋1＋√K/NθKN-N＋1,N〈1.Moreover,the performance of OMMP for support recovery from noisy observations is also discussed.It is shown that,for l_2 bounded and l_∞bounded noisy cases,OMMP can recover the true support of any K-sparse signal under conditions on the restricted isometry property of the sampling matrixφand the minimum magnitude of the nonzero components of the signal.展开更多
This paper discusses conditions under which the solution of linear system with minimal Schatten-p norm, 0 〈 p ≤ 1, is also the lowest-rank solution of this linear system. To study this problem, an important tool is ...This paper discusses conditions under which the solution of linear system with minimal Schatten-p norm, 0 〈 p ≤ 1, is also the lowest-rank solution of this linear system. To study this problem, an important tool is the restricted isometry constant （RIC）. Some papers provided the upper bounds of RIC to guarantee that the nuclear-norm minimization stably recovers a low-rank matrix. For example, Fazel improved the upper bounds to δ4Ar 〈 0.558 and δ3rA 〈 0.4721, respectively. Recently, the upper bounds of RIC can be improved to δ2rA 〈 0.307. In fact, by using some methods, the upper bounds of RIC can be improved to δ2tA 〈 0.4931 and δrA 〈 0.309. In this paper, we focus on the lower bounds of RIC, we show that there exists linear maps A with δ2rA 〉1√2 or δrA 〉 1/3 for which nuclear norm recovery fail on some matrix with rank at most r. These results indicate that there is only a little limited room for improving the upper bounds for δ2rA and δrA.Furthermore, we also discuss the upper bound of restricted isometry constant associated with linear maps A for Schatten p （0 〈 p 〈 1） quasi norm minimization problem.展开更多
基金supported by the Science Foundation of Guangdong University of Finance & Economics(Grant No.13GJPY11002)National Natural Science Foundation of China(Grant Nos.11071031,11271060,11290143,U0935004 and U1135003)+1 种基金the Guangdong Natural Science Foundation(Grant No.S2012010010376)the Guangdong University and Colleges Technology Innovation Projects(Grant No.2012KJCX0048)
文摘Orthogonal multi-matching pursuit（OMMP）is a natural extension of orthogonal matching pursuit（OMP）in the sense that N（N≥1）indices are selected per iteration instead of 1.In this paper,the theoretical performance of OMMP under the restricted isometry property（RIP）is presented.We demonstrate that OMMP can exactly recover any K-sparse signal from fewer observations y=φx,provided that the sampling matrixφsatisfiesδKN-N＋1＋√K/NθKN-N＋1,N〈1.Moreover,the performance of OMMP for support recovery from noisy observations is also discussed.It is shown that,for l_2 bounded and l_∞bounded noisy cases,OMMP can recover the true support of any K-sparse signal under conditions on the restricted isometry property of the sampling matrixφand the minimum magnitude of the nonzero components of the signal.
基金supported by National Natural Science Foundation of China (Grant Nos.91130009, 11171299 and 11041005)National Natural Science Foundation of Zhejiang Province in China (Grant Nos. Y6090091 and Y6090641)
文摘This paper discusses conditions under which the solution of linear system with minimal Schatten-p norm, 0 〈 p ≤ 1, is also the lowest-rank solution of this linear system. To study this problem, an important tool is the restricted isometry constant （RIC）. Some papers provided the upper bounds of RIC to guarantee that the nuclear-norm minimization stably recovers a low-rank matrix. For example, Fazel improved the upper bounds to δ4Ar 〈 0.558 and δ3rA 〈 0.4721, respectively. Recently, the upper bounds of RIC can be improved to δ2rA 〈 0.307. In fact, by using some methods, the upper bounds of RIC can be improved to δ2tA 〈 0.4931 and δrA 〈 0.309. In this paper, we focus on the lower bounds of RIC, we show that there exists linear maps A with δ2rA 〉1√2 or δrA 〉 1/3 for which nuclear norm recovery fail on some matrix with rank at most r. These results indicate that there is only a little limited room for improving the upper bounds for δ2rA and δrA.Furthermore, we also discuss the upper bound of restricted isometry constant associated with linear maps A for Schatten p （0 〈 p 〈 1） quasi norm minimization problem.
