Hankel matrix nuclear norm regularized tensor completion for N-dimensional exponential signals (中文，English)
Jiaxi Ying1, Hengfa Lu1, Qingtao Wei4, Jian-Feng Cai2, Di Guo3, Jihui Wu4, Zhong Chen1, Xiaobo Qu1,*
1 Department of Electronic Science, Fujian Provincial Key Laboratory of Plasma and Magnetic Resonance, Xiamen University, Xiamen, China
2 Department of Mathematics, Hong Kong University of Science and Technology, Hong Kong, China
3 School of Computer and Information Engineering, Xiamen University of Technology, Xiamen, China
4
School of Life Sciences, University of Science and Technology of China, Hefei, China.
* Email: quxiaobo <at> xmu.edu.cn or quxiaobo2009 <at> gmail.com.
Signals are generally modeled as a superposition of exponential functions in spectroscopy of chemistry, biology, and medical imaging. For fast data acquisition or other inevitable reasons, however, only a small amount of samples may be acquired, and how to recover the full signal becomes an active research topic. However, existing exponential signal recovery, such as low rank Hankel matrix recovery [1] and enhanced matrix recovery, cannot efficiently recover N-dimensional exponential signals with N ≥ 3.
In this work, we study the problem of recovering N-dimensional (particularly N ≥ 3) exponential signals from partial observations, and formulate this problem as a low-rank tensor completion problem with exponential factor vectors. The full signal is reconstructed by simultaneously exploiting the CANDECOMP/PARAFAC tensor structure and the exponential structure of the associated factor vectors. The latter is promoted by minimizing an objective function involving the nuclear norm of Hankel matrices. A numerical algorithm is developed to solve the proposed model and its convergence is theoretically analyzed.
Experimental results on simulated and real magnetic resonance spectroscopy data show that the proposed approach can successfully recover full signals from very limited samples and is robust to the estimated tensor rank.
This work aims to reconstruct N-dimensional (particularly N ≥ 3) exponential signals. Figure 1, for example, shows a graphical illustration of a 3-dimensional exponential signal.
We proposed the following reconstruction model
where lambda is a regularization parameter that trades off the nuclear norm against the data consistency and 
is a linear operator, mapping an vector to a Hankel matrix.
To solve the reconstruction model above, we develop an algorithm based on alternating direction method of multipliers (ADMM). We demonstrate that the sequence generated by the algorithm converges. Furthermore, if we further impose some condition on the Lagrange multipliers, then the limit is a critical point.
We apply HMRTC to recover a 3-D simulated data and protein RNA spectrum. Figure 2 shows that HMRTC yields an average relative reconstruction error that is much smaller than ADM-TR and WCP. Figure 3 shows the 1H-13C and 1H-15N skyline projection spectra of HNCO spectrum, which indicates that HMRTC can achieve high quality of reconstruction obtained from only 10% of the fully sampled.
The demo code of HMRTC can be downloaded here.
Dataset: The 3D HNCO can be download here.
A 3-D HNCO spectrum is tested and its sample is the U-[15N, 13C] RNA recognition motifs domain of protein RNA binding motif protein 5, which is a component of the spliceosome A-complex. The ADM-TR, WCP and HMRTC are compared in recovering this 3-D spectrum with the size of 64 ×128×512 from a 3-D Poisson-gap nonuniformly sampled time domain data. All the spectra are processed in NMRPipe using a routine processing manner.
Please cite this paper when using the HMRTC code. This citation is :
Jiaxi Ying, Hengfa Lu, Qingtao Wei, Jian-Feng Cai, Di Guo, Jihui Wu, Zhong Chen, Xiaobo Qu*, Hankel matrix nuclear norm regularized tensor completion for N-dimensional exponential signals. IEEE Transactions on Signal Processing, 65(14): 3702-3717, 2017.
This work was partially supported by NSFC (61571380, 61672335, 61601276 and U1632274), Important Joint Research Project on Major Diseases of Xiamen City (3502Z20149032), Fundamental Research Funds for the Central Universities (20720150109) and the Natural Science Foundation of Fujian Province of China (2015J01346 and 2016J05205). The authors would like to thank Silvia Gandy, Gongguo Tang, Ji Liu, Xinhua Zhang and Andreas Jakobsson for sharing codes for comparisons and Weiyu Xu for helpful discussions. The authors also appreciate reviewers and editors for their constructive comments.
[1] X. Qu, M. Mayzel, J.-F. Cai, Z. Chen, and V. Orekhov, “Accelerated NMR spectroscopy with low-rank reconstruction,” Angew. Chem. Int. Ed., vol. 54, pp. 852-854, 2015.
[2] X. Qu, X. Cao, D. Guo, and Z. Chen. “Compressed sensing for sparse magnetic resonance spectroscopy,” Int. Society for Magn. Reson. in Med. 18th Sci. Meeting, Stockholm, Sweden, pp. 3371, 2010.
[3] X. Qu, D. Guo, X. Cao, S. Cai, and Z. Chen, “Reconstruction of self-sparse 2D NMR spectra from undersampled data in the indirect dimension,” Sensors, vol. 11, pp. 8888-8909, 2011.
[4] E. J. Cand`es and C. Fernandez-Granda, “Towards a mathematical theory of super-resolution,” Commun. Pure Appl. Math., vol. 67, pp. 906-956, 2014.
[5] G. Tang, B. N. Bhaskar, P. Shah, and B. Recht, “Compressed sensing off the grid,” IEEE Trans. Inf. Theory, vol. 59, pp. 7465-7490, 2013.
[6] D. Nion and N. D. Sidiropoulos, “Tensor algebra and multidimensional harmonic retrieval in signal processing for MIMO radar,” IEEE Trans. Signal Process., vol. 58, pp. 5693-5705, 2010.
[7] F. Wen and H. C. So, “Robust multi-dimensional harmonic retrieval using iteratively reweighted HOSVD,” IEEE Signal Process. Lett., vol. 22, pp. 2464-2468, 2015.
[8] M. Haardt and J. A. Nossek, “Simultaneous Schur decomposition of several nonsymmetric matrices to achieve automatic pairing in multidimensional harmonic retrieval problems,” IEEE Trans. Signal Process., vol. 46, pp. 161-169, 1998.
[9] Y. Chi and Y. Chen, “Compressive two-dimensional harmonic retrieval via atomic norm minimization,” IEEE Trans. Signal Process., vol. 63, pp. 1030-1042, 2015.
[10] J. A. Tropp, J. N. Laska, M. F. Duarte, J. K. Romberg, and R. G. Baraniuk, “Beyond nyquist: Efficient sampling of sparse bandlimited signals,” IEEE Trans. Inf. Theory, vol. 56, pp. 520-544, 2010.
[11] M. Lustig, D. Donoho, and J. M. Pauly, “Sparse MRI: The application of compressed sensing for rapid MR imaging,” Magn. Reson. Med, vol. 58, pp. 1182-1195, 2007.
[12] F. Lam and Z.-P. Liang, “A subspace approach to high-resolution spectroscopic imaging” Magn. Reson. Med, vol. 71, pp. 1349-1357, 2014.
[13] X. Qu, D. Guo, B. Ning, Y. Hou, Y. Lin, S. Cai, Z. Chen, “Undersampled MRI reconstruction with patch-based directional wavelets,” Magn. Reson. Imag., vol. 30, pp. 964977, 2012
[14] X. Qu, Y. Hou, F. Lam, D. Guo, J. Zhong, and Z. Chen, “Magnetic resonance image reconstruction from undersampled measurements using a patch-based nonlocal operator,” Med. Image Anal., vol. 18, pp. 843856, 2014.
[15] Y. Liu, Z. Zhan, J.-F. Cai, D. Guo, Z. Chen, X. Qu, “Projected iterative soft-thresholding algorithm for tight frames in compressed sensing magnetic resonance imaging,” IEEE Trans. Med. Imag., vol. 35, 2130-2140, 2016.
[16] Y. Li, J. Razavilar, and K. J. R. Liu, “A high-resolution technique for multidimensional NMR spectroscopy,” IEEE Trans. Biomed. Eng., vol. 45, pp. 78-86, 1998.
[17] W. Xu, J.-F. Cai, K. V. Mishra, C. Myung, and A. Kruger, “Precise semidefinite programming formulation of atomic norm minimization for recovering d-dimensional (d_ 2) off-the-grid frequencies,” in Proc. IEEE Inf. Theory Appl. Workshop (ITA), pp. 1-4, 2014.
[18] K. V. Mishra, M. Cho, A. Kruger, and W. Xu, “Spectral super-resolution with prior knowledge,” IEEE Trans. Signal Process., vol. 63, pp. 5342- 5357, 2015.
[19] M. Cho, K. V. Mishra, J. F. Cai, and W. Xu, “Block iterative reweighted algorithms for super-resolution of spectrally sparse signals,” IEEE Signal Process. Lett., vol. 22, pp. 2319-2313, 2015.
[20] Z. Tan, Y. C. Eldar, and A. Nehorai, “Direction of arrival estimation using co-prime arrays: A super resolution viewpoint,” IEEE Trans. Signal Process., vol. 62, pp. 5565-5576, 2014.
[21] E. J. Cand`es, J. Romberg, and T. Tao, “Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,” IEEE Trans. Inf. Theory, vol. 52, pp. 489-509, 2006.
[22] Y. Chi, L. L. Scharf, A. Pezeshki, and A. R. Calderbank, “Sensitivity to basis mismatch in compressed sensing,” IEEE Trans. Signal Process., vol. 59, pp. 2182-2195, 2011.
[23] V. Chandrasekaran, B. Recht, P. Parrilo, and A. Willsky, “The convex geometry of linear inverse problems,” Found. Comut. Math., vol. 12, pp. 805-849, 2012.
[24] Y. Hua and T. K. Sarkar, “Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise,” IEEE Trans. Acoust., Speech and Signal Process., vol. 38, pp. 814-824, 1990.
[25] E. J. Cand`es and B. Recht, “Exact matrix completion via convex optimization,” Found. Comut. Math., vol. 9, pp. 717-772, 2009.
[26] R. H. Keshavan, A. Montanari, and O. Sewoong, “Matrix completion from a few entries,” IEEE Trans. Inf. Theory, vol. 56, pp. 2980-2998, 2010.
[27] J.-F. Cai, X. Qu, W. Xu, and G.-B. Ye, “Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction,” Appl. Comput. Harmon. Anal., vol. 41, pp. 470-490, 2016.
[28] J.-F. Cai, S. Liu, and W. Xu, “A fast algorithm for reconstruction of spectrally sparse signals in super-resolution,” Proc. of SPIE, Wavelets and Sparsity XVI, vol. 9597, 2015.
[29] F. Andersson, M. Carlsson, J. Y. Tourneret, and H. Wendt, “A new frequency estimation method for equally and unequally spaced data,” IEEE Trans. Signal Process., vol. 62, pp. 5761-5774, 2014.
[30] M. Fazel, T. K. Pong, D. Sun, and P. Tseng, “Hankel matrix rank minimization with applications to system identification and realization,” SIAM J. Matrix Anal. Appl., vol. 34, pp. 946-977, 2013.
[31] I. Markovsky and K. Usevich, “Structured low-rank approximation with missing data,” SIAM J. Matrix Anal. Appl., vol. 34, pp. 814-830, 2013.
[32] K. Usevich and P. Comon, “Hankel low-rank matrix completion: Performance of the nuclear norm relaxation,” IEEE J. Sel. Top. Signal Process., vol. 10, pp. 637-646, 2016.
[33] K. Kazimierczuk and V. Orekhov, “Accelerated NMR spectroscopy by using compressed sensing,” Angew. Chem. Int. Ed., vol. 123, pp. 5670-5673, 2011.
[34] D. J. Holland, M. J. Bostock, L. F. Gladden, and D. Nietlispach, “Fast multidimensional NMR spectroscopy using compressed sensing,” Angew. Chem. Int. Ed., vol. 50, pp. 6548-6551, 2011.
[35] Y. Chen and Y. Chi, “Robust spectral compressed sensing via structured matrix completion,” IEEE Trans. Inf. Theory, vol. 60, pp. 6576-6601, 2014.
[36] J. Liu, P. Musialski, P. Wonka, and J. Ye, “Tensor completion for estimating missing values in visual data,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 35, pp. 208-220, 2013.
[37] Y. Liu, F. Shang, L. Jiao, J. Cheng, and H. Cheng, “Trace norm regularized CANDECOMP/PARAFAC decomposition with missing data,” IEEE Trans. Cybern., vol. 45, pp. 2437-2448, 2015.
[38] S. Gandy, B. Recht, and I. Yamada, “Tensor completion and low-n rank tensor recovery via convex optimization,” Inverse Probl., vol. 27, pp. 025010, 2011.
[39] E. Acar, D. M. Dunlavy, T. G. Kolda, and M. Mørup, “Scalable tensor factorizations for incomplete data,” Chemometr. Intell. Lab. Syst., vol. 106, pp. 41-56, 2011.
[40] G. Tomasi and R. Bro, “PARAFAC and missing values,” Chemometr. Intell. Lab. Syst., vol. 75, pp. 163-180, 2005.
[41] M. Yuan and C.-H. Zhang, “On tensor completion via nuclear norm minimization”. Found. Comut. Math., vol. 7, pp. 1-38, 2014.
[42] M. Signoretto, L. D. Lathauwer, and J. A. K. Suykens, “Nuclear norms for tensors and their use for convex multilinear estimation,” Tech. Rep. 10-186, K.U.Leuven, 2010.
[43] L. Yang, Z. H. Huang, and X. Shi, “A fixed point iterative method for low n-rank tensor pursuit,” IEEE Trans. Signal Process., vol. 61, pp.2952–2962, 2013.
[44] T. G. Kolda and B. W. Bader, “Tensor decompositions and applications,” SIAM Rev., vol. 51, pp. 455-500, 2009.
[45] J. D. Carroll and J.-J. Chang, “Analysis of individual differences in multidimensional scaling via an n-way generalization of Eckart-Young decomposition,” Psychometrika, vol. 35, pp. 283-319, 1970.
[46] T. G. Kolda, “Multilinear operators for higher-order decompositions,” Tech. Rep. SAND2006-2081, Sandia National Laboratories, 2006.
[47] Y. Yu, H. Cheng and X. Zhang, “Approximate low-rank tensor learning”, 32nd NIPS Workshop on Optimization for Machine Learning, JMLR Workshop Conf. Proc. 37, 2014.
[48] Q. Li, A. Prater, L. Shen and G. Tang, “Overcomplete tensor decomposition via convex optimization,” Arxiv: 1602.08614, 2016.
[49] J.-F. Cai, E. J. Cand`es, and Z. Shen, “A singular value thresholding algorithm for matrix completion,” SIAM J. Optim., vol. 20, pp. 1956-1982, 2010.
[50] A. S. Stern, D. L. Donoho, and J. C. Hoch, “NMR data processing using iterative thresholding and minimum l1-norm reconstruction,” J. Magn. Reson., vol. 188, pp. 295-300, 2007.
[51] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends Mach. Learn., vol. 3, pp. 1-122, 2011.
[52] Z. Zhan, J.-F. Cai, D. Guo, Y. Liu, Z. Chen and X. Qu, “Fast multiclass dictionaries learning with geometrical directions in MRI reconstruction,” IEEE Trans. Biomed. Eng., vol. 63, pp. 1850-1861, 2016.
[53] M. V. B. Laurent Sorber and Lieven De Lathauwer, “Tensorlab v2.0,” 2014.
[54] Z. Lin, M. Chen, and Y. Ma, “The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices,” UIUC Technical Report UILU-ENG-09-2215.
[55] Y.-L. Chen, C.-T. Hsu, and H.-Y. Liao, “Simultaneous tensor decomposition and completion using factor priors,” IEEE Trans. Pattern Anal. Mach.Intell., vol. 36, pp. 577-591, 2014.
[56] S. G. Hyberts, K. Takeuchi, and G. Wagner, “Poisson-Gap sampling and forward maximum entropy reconstruction for enhancing the resolution and sensitivity of protein NMR data,” J. Am. Chem. Soc., vol. 132, pp.2145-2147, 2010.
[57] M. Mobli, “Reducing seed dependent variability of non-uniformly sampled multidimensional NMR data,” J. Magn. Reson. , vol. 256, pp. 60-69, 2015 .
[58] V. Orekhov and V. A. Jaravine, “Analysis of non-uniformly sampled spectra with multi-dimensional decomposition,” Prog. Nucl. Magn. Reson. Spectrosc., vol. 59, pp. 271-292, 2011.
[59] Z. Song, P. Wu, P. Ji, J. Zhang, Q. Gong, J. Wu, and Y. Shi, “Solution structure of the second RRM domain of RBM5 and its unusual binding characters for different RNA targets,” Biochemistry, vol. 51, pp. 6667–78, 2012.
[60] F. Delaglio, S. Grzesiek, G.W. Vuister, G. Zhu, J. Pfeifer, and A. Bax, “NMRPipe: A multidimensional spectral processing system based on Unix pipes,” J. Biomol. NMR, vol. 6, pp. 277-293, 1995.
[61] B. Bl¨umich and D. Ziessow, “Skyline projections in two-dimensional NMR spectroscopy,” J. Magn. Reson., vol. 49, pp. 151-154, 1982.
[62] J. Sw¨ard, S. I. Adalbj¨ornsson and A. Jakobsson, “High resolution sparse estimation of exponentially decaying N-dimensional signals,” Signal Process., vol. 128, pp. 309–317, 2016.
[63] V. Y. Orekhov, I. V. Ibraghimov, and M. Billeter, “MUNIN: A new approach to multi-dimensional NMR spectra interpretation,” J. Biomol. NMR, vol. 20, pp. 49–60, 2001.
[64] E. Acar, D. M. Dunlavy, T. G. Kolda, and M. Mørup, “Scalable tensor factorizations with missing data,” in Proc. SIAM International Conference on Data Mining, 2010, pp. 701-712.
[65] S. Burer and R. D. Monteiro, “Local minima and convergence in low rank semidefinite programming,” Math. Program., vol. 103, pp. 427-444, 2005.
[66] M. Mardani, G. Mateos, and G. B. Giannakis, “Subspace learning and imputation for streaming big data matrices and tensors,” IEEE Trans. Signal Process., vol. 63, pp. 2663–2677, 2015.
[67] N. Srebro and A. Shraibman, “Rank, trace-norm and max-norm,” in Proc. of Learning Theory, pp. 545-560, 2005.