Hankel matrix nuclear norm regularized tensor completion for N-dimensional exponential signals (中文，English)
应佳熙1, 鲁恒发1, 魏晴涛4, 蔡剑锋2, 郭迪3, 吴季辉4, 陈忠1, 屈小波1,*
1 厦门大学，电子科学系，福建等离子体与磁共振重点研究实验室，中国，厦门；
2 香港科技大学，数学系，中国，香港;
3 厦门理工学院，计算机与信息工程学院，中国，厦门;
4 中国科技大学，生命科学学院，中国，合肥。
* Email: quxiaobo <at> xmu.edu.cn 或 quxiaobo2009 <at> gmail.com.
在生物、化学和医学成像中，成像信号通常可以建模成一系列指数函数的叠加。由于加速采样或其它不可避免的原因，实际采样得到的信号有时不能满足奈奎斯特准则，导致采集数据丢失从而造成信号失真。如何从含数据丢失的信号中重建出完整的信号是当前信号处理领域的研究热点之一。但目前前沿的指数信号重建方法，如低秩Hankel矩阵补全 [1, 2]和块Hankel矩阵补全，无法有效地重建高维N（N≥ 3维）指数信号。 本文提出了一种重建方法来从少量采集数据中恢复N (N ≥ 3)维指数信号。该方法同时利用的低CP（CANDECOMP/PARAFAC，张量）秩结构和其对应的因子向量的指数结构。为了施加低CP（CANDECOMP/PARAFAC，张量）秩结构，我们把信号表达成CP（CANDECOMP/PARAFAC，张量）分解的形式并且运用了最小二乘法去匹配采样得到的数据。为了施加其因子向量的指数结构，我们把因子矩阵的每一列列都排列成Hankel 矩阵并施加核范数作为正则项。我们用提出的方法重建仿真的指数信号和实测的磁共振波谱数据，实验结果表明该方法可以从非常少量的采集数据中恢复出可靠的信号，并且重建信号所需的采集数据量远小于对比的典型张量重建方法。
本文旨在重建N (N ≥ 3)维指数信号。比如，3维指数信号如图1所示。
我们提出以下的重建模型
其中lambda是正则化参数，用于平衡核范数项和数据匹配项。
为了求解以上的重建模型，我们提出了一个基于交替方向乘子的数值算法。我们在理论上证明算法产生的序列是收敛的，并且在一定条件下，算法极限点收敛于驻点。
是一个线性算子，把一个向量排列成一个Hankel矩阵。
我们用仿真指数信号和实测的三维磁共振波谱。图1表明，本文提出的方法得到的相对重建误差远小于典型的张量重建方法ADM-TR[4]和WCP[5]。图2展示了三维HNCO谱的1H-13C和1H-15N投影谱，可以看出提出的方法可以在10%采样率下实现高质量的重建，有效地降低了实验采集时间。
点击该链接下载本文方法的MATLAB代码。
点击该链接下载本文的3D HNCO数据。
凡是有用本文的程序或者其修改版，请引用该论文。本文的引文格式如下：
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.
本工作受到以下基金的支持：国家自然科学基金(61571380, 61672335, 61601276和U1632274), 厦门市重要重大疾病联合攻关项目(3502Z20149032), 中央高校基本科研业务费专项资金 (20720150109)和福建省自然科学基金(2015J01346和2016J05205). 作者感谢Silvia Gandy, Gongguo Tang, Ji Liu, Xinhua Zhang和Andreas Jakobsson分享对比实验中的代码，也感谢Weiyu Xu有益的讨论，以及审稿人和编辑有建设性的评论。
[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.