压缩传感理论、优化算法及其在系统状态重构中应用
|
摘要
分别对压缩传感理论、优化算法及其在系统状态重构中的应用3个方面进行了研究.在压缩传感理论方面,包括对所压缩信号的稀疏或低秩要求、编码测量以及与优化算法之间的关系进行了较为深入的研究,重点分析了原始信号的稀疏与低秩之间的关系、测量矩阵与压缩矩阵之间的关系、满足限制等距特性(RIP)的测量矩阵,以及由压缩传感理论提供的最少测量次数.在压缩信号重构过程中所需要采用的优化算法,着重讨论了核函数的凸优化问题描述,分别对常用的优化算法,包括最小二乘(LS)法、最大熵法、极大似然法和贝叶斯方法的求解过程中所用到的性能指标、优化目标和求解条件等进行了归纳与特性分析.对量子态估计中的交替方向乘子法(ADMM)以及作者最新提出的迭代阈值收缩法(IST)进行了专门的性能对比,并通过量子位分别5、6和7情况下纯态估计的应用为例,对不同测量比率对参数估计性能的影响,以及算法在不同量子位数下性能的表现,进行了不同层次上的对比和分析,完整地阐述基于压缩传感理论与优化的系统参数估计的研究过程.
This paper studies three aspects of compressive sensing theory,optimization algorithms,and their applications in system state reconstruction. In compressive sensing theory,the relationship between the sparse and low rank of the compressed signal is studied,together with signal measurement and their relationship with the optimization algorithm. We focus on the analysis of the sparse original signal and the relationship between low rank; the relationship between the measurement matrix and the matrix compression,the measurement matrix satisfied the restricted isometry property( RIP),and the minimum number of measurements provided by the compressive sensing theory. The convex optimization problem of kernel function is discussed with respect to optimization algorithms used in reconstruction of the compressed signal. Characteristics of traditional optimization algorithms,including the least squares( LS) method,maximum entropy method,maximum likelihood method,and bias method are summarized and analyzed in the process of solving the performance index,optimization goal,and solution conditions. The alternating direction multiplier method( ADMM) and iterative threshold shrinkage method( IST) are also used to estimate quantum states,and application examples of pure state estimations with 5,6,and 7 qubits are assumed. In addition,the effects of parameter estimation performances with different measurement rates and different algorithms in different qubits are compared on different levels. Finally,the research process used in system parameter estimation is fully explained based on optimization and compressive sensing theory.
This paper studies three aspects of compressive sensing theory,optimization algorithms,and their applications in system state reconstruction. In compressive sensing theory,the relationship between the sparse and low rank of the compressed signal is studied,together with signal measurement and their relationship with the optimization algorithm. We focus on the analysis of the sparse original signal and the relationship between low rank; the relationship between the measurement matrix and the matrix compression,the measurement matrix satisfied the restricted isometry property( RIP),and the minimum number of measurements provided by the compressive sensing theory. The convex optimization problem of kernel function is discussed with respect to optimization algorithms used in reconstruction of the compressed signal. Characteristics of traditional optimization algorithms,including the least squares( LS) method,maximum entropy method,maximum likelihood method,and bias method are summarized and analyzed in the process of solving the performance index,optimization goal,and solution conditions. The alternating direction multiplier method( ADMM) and iterative threshold shrinkage method( IST) are also used to estimate quantum states,and application examples of pure state estimations with 5,6,and 7 qubits are assumed. In addition,the effects of parameter estimation performances with different measurement rates and different algorithms in different qubits are compared on different levels. Finally,the research process used in system parameter estimation is fully explained based on optimization and compressive sensing theory.
引文
[1]Candes E,Romberg J.Sparsity and incoherence in compressive sampling[J].Inverse Problems,2007,23(3):969-985.
[2]Candes E J,Tao T.Decoding by linear programming[J].IEEE Transactions on Information Theory,2005,51(12):4203-4215.
[3]Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.
[4]Candes E J.The restricted isometry property and its implications for compressed sensing[J].Comptes Rendus Mathematique,2008,346(9):589-592.
[5]Baumgratz T,Gross D,Cramer M,et al.Scalable reconstruction of density matrices[J].Physical Review Letters,2013,111(2):020401.
[6]Flammia S T,Gross D,Liu Y K,et al.Quantum tomography via compressed sensing:Error bounds,sample complexity and efficient estimators[J].New Journal of Physics,2012,14(9):095022.
[7]Lloyd S,Mohseni M,Rebentrost P.Quantum principal component analysis[J].Nature Physics,2014,10(9):631-633.
[8]Ferrie C.Self-guided quantum tomography[J].Physical review letters,2014,113(19):190404.
[9]Gross D,Liu Y K,Flammia S T,et al.Quantum state tomography via compressed sensing[J].Physical Review Letters,2010,105(15):150401.
[10]Shabani A,Kosut R L,Mohseni M,et al.Efficient measurement of quantum dynamics via compressive sensing[J].Physical Review Letters,2011,106(10):100401.
[11]Liu W T,Zhang T,Liu J Y,et al.Experimental quantum state tomography via compressed sampling[J].Physical Review Letters,2012,108(17):170403.
[12]Smith A,Riofrío C A,Anderson B E,et al.Quantum state tomography by continuous measurement and compressed sensing[J].Physical Review A,2013,87(3):030102.
[13]Qi B,Hou Z,Li L,et al.Quantum state tomography via linear regression estimation[J].Scientific Reports,2013,3:3496.
[14]Li K,Cong S.A robust compressive quantum state tomography algorithm using ADMM[C]//Preprint of the 19th World Congress of the International Federation of Automation Control.Piscataway,NJ,USA:IEEE,2014:6878-6883.
[15]Gabay D,Mercier B.A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J].Computers&Mathematics with Applications,1976,2(1):17-40.
[16]Boyd S,Parikh N,Chu E,et al.Distributed optimization and statistical learning via the alternating direction method of multipliers[J].Foundations and Trends in Machine Learning,2011,3(1):1-122.
[17]Yuan X,Yang J.Sparse and low-rank matrix decomposition via alternating direction methods[J].Pacific journal of optimization,2013,9(1):167-180.
[18]Yang J,Zhang Y.Alternating direction algorithms for l1-problems in compressive sensing[J].SIAM Journal on Scientific Computing,2011,33(1):250-278.
[19]Koh K,Kim S J,Boyd S.An interior-point method for large-scale ll-regularized logistic regression[J].Journal of Machine Learning Research,2007,8(7):1519-1555.
[20]Nowak R D,Wright S J.Gradient projection for sparse reconstruction:Application to compressed sensing and other inverse problems[J].IEEE Journal of selected topics in signal processing,2007,1(4):586-597.
[21]张娇娇,丛爽,郑凯,等.进一步改进的交替方向乘子法及其在量子态估计的应用[C]//第17届中国系统仿真技术及其应用年会.北京:中国系统工程学会,2016:82-87.Zhang J J,Cong S,Zheng K,et al.Further improved ADMM and its application in quantum state estimation[C]//Proceedings of 17th Chinese Conference on System Simulation Technology&Application(CCSSTA 2016).Beijing:System Engineering Society of China,2016:82-87.
[22]杨靖北,丛爽.量子层析中的几种量子状态估计方法的研究[J].系统科学与数学,2014,34(12):1532-1546.Yang J B,Cong S.Research on several quantum state estimation methods of quantum tomography[J].Journal of Systems Sciences and Mathematical Sciences,2014,34(12):1532-1546.
[23]李树涛,魏丹.压缩传感综述[J].自动化学报,2009,25(11):1369-1377.Li S T,Wei D.A survey on compressive sensing[J].Acta Automatica Sinica,2009,25(11):1369-1377.
[24]杨海蓉,张成,丁大为,等.压缩传感理论与重构算法[J].电子学报,2011,39(1):142-148.Yang H R,Zhang C,Ding D W,et al.The theory of compressed sensing and reconstruction algorithm[J].Acta Electronica Sinica,2011,39(1):142-148.
[25]李波,谢杰镇,王博亮.基于压缩传感理论的数据重建[J].计算机技术与发展,2009,19(5):23-29.Li B,Xie J Z,Wan B L.Signal reconstruction based on compressed sensing[J].Computer Technology and Development,2009,19(5):23-29.
[26]杨振亚,郑楚君.基于压缩传感的纯相位物体相位恢复[J].物理学报,2013,62(10):104203-1-104203-6.Yang Z Y,Zheng C J.Phase retrieval of pure phase object based on compressed sensing[J].Acta Physics Sinica,2013,62(10):104203-1-104203-6.
[27]丛爽,李克之.压缩传感理论及其在量子态估计中的应用[C]//第16届中国中国系统仿真技术及其应用年会.北京:中国系统工程学会,2015:307-311.Cong S,Li K Z.Compression sensing theory and its application in quantum state estimation[C]//Proceedings of 16th Chinese Conference on System Simulation Technology&Application(CCSSTA 2015).Beijing:System Engineering Society of China,2015:307-311.
[28]Recht B,Fazel M,Parrilo P A.Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[J].SIAM Review,2010,52(3):471-501.
[29]Candes E J,Plan Y.Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements[J].IEEE Transactions on Information Theory,2011,57(4):2342-2359.
[30]Liu Y K.Universal low-rank matrix recovery from Pauli measurements[C]//Advances in Neural Information Processing Systems.Berlin,Germnay:Springer,2011:1638-1646.
[31]Zheng K,Li K Z,Cong S.Characteristics optimization via compressed sensing in quantum state estimation[C]//Proceedings of the 2016 IEEE Multi-Conference on Systems and Control(MSC2016).Piscataway,NJ,USA:IEEE,2016:948-953.
[32]丛爽,张慧,李克之.基于压缩传感的量子状态估计算法的性能对比[J].模式识别与人工智能,2016,29(2):116-121.Cong S,Zhang H,Li K Z.Comparative study of quantum state estimation algorithm based on compressive sensing[J].Pattern Recognition and Artificial Intelligence,2016,29(2):116-121.
[33]Heinosaari T,Mazzarella L,Wolf M M.Quantum tomography under prior information[J].Communications in Mathematical Physics,2013,318(2):355-374.
[34]Liu W T,Zhang T,Liu J Y,et al.Experimental quantum state tomography via compressed sampling[J].Physical Review Letters,2012,108(17):170403.
[35]Baldwin C,Kalev A,Deutsch I.Quantum process estimation via compressed sensing with convex optimization[J].Bulletin of the American Physical Society,2014.
[36]Banaszek K,Cramer M,Gross D.Focus on quantum tomography[J].New Journal of Physics,2013,15(12):125020.
[2]Candes E J,Tao T.Decoding by linear programming[J].IEEE Transactions on Information Theory,2005,51(12):4203-4215.
[3]Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.
[4]Candes E J.The restricted isometry property and its implications for compressed sensing[J].Comptes Rendus Mathematique,2008,346(9):589-592.
[5]Baumgratz T,Gross D,Cramer M,et al.Scalable reconstruction of density matrices[J].Physical Review Letters,2013,111(2):020401.
[6]Flammia S T,Gross D,Liu Y K,et al.Quantum tomography via compressed sensing:Error bounds,sample complexity and efficient estimators[J].New Journal of Physics,2012,14(9):095022.
[7]Lloyd S,Mohseni M,Rebentrost P.Quantum principal component analysis[J].Nature Physics,2014,10(9):631-633.
[8]Ferrie C.Self-guided quantum tomography[J].Physical review letters,2014,113(19):190404.
[9]Gross D,Liu Y K,Flammia S T,et al.Quantum state tomography via compressed sensing[J].Physical Review Letters,2010,105(15):150401.
[10]Shabani A,Kosut R L,Mohseni M,et al.Efficient measurement of quantum dynamics via compressive sensing[J].Physical Review Letters,2011,106(10):100401.
[11]Liu W T,Zhang T,Liu J Y,et al.Experimental quantum state tomography via compressed sampling[J].Physical Review Letters,2012,108(17):170403.
[12]Smith A,Riofrío C A,Anderson B E,et al.Quantum state tomography by continuous measurement and compressed sensing[J].Physical Review A,2013,87(3):030102.
[13]Qi B,Hou Z,Li L,et al.Quantum state tomography via linear regression estimation[J].Scientific Reports,2013,3:3496.
[14]Li K,Cong S.A robust compressive quantum state tomography algorithm using ADMM[C]//Preprint of the 19th World Congress of the International Federation of Automation Control.Piscataway,NJ,USA:IEEE,2014:6878-6883.
[15]Gabay D,Mercier B.A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J].Computers&Mathematics with Applications,1976,2(1):17-40.
[16]Boyd S,Parikh N,Chu E,et al.Distributed optimization and statistical learning via the alternating direction method of multipliers[J].Foundations and Trends in Machine Learning,2011,3(1):1-122.
[17]Yuan X,Yang J.Sparse and low-rank matrix decomposition via alternating direction methods[J].Pacific journal of optimization,2013,9(1):167-180.
[18]Yang J,Zhang Y.Alternating direction algorithms for l1-problems in compressive sensing[J].SIAM Journal on Scientific Computing,2011,33(1):250-278.
[19]Koh K,Kim S J,Boyd S.An interior-point method for large-scale ll-regularized logistic regression[J].Journal of Machine Learning Research,2007,8(7):1519-1555.
[20]Nowak R D,Wright S J.Gradient projection for sparse reconstruction:Application to compressed sensing and other inverse problems[J].IEEE Journal of selected topics in signal processing,2007,1(4):586-597.
[21]张娇娇,丛爽,郑凯,等.进一步改进的交替方向乘子法及其在量子态估计的应用[C]//第17届中国系统仿真技术及其应用年会.北京:中国系统工程学会,2016:82-87.Zhang J J,Cong S,Zheng K,et al.Further improved ADMM and its application in quantum state estimation[C]//Proceedings of 17th Chinese Conference on System Simulation Technology&Application(CCSSTA 2016).Beijing:System Engineering Society of China,2016:82-87.
[22]杨靖北,丛爽.量子层析中的几种量子状态估计方法的研究[J].系统科学与数学,2014,34(12):1532-1546.Yang J B,Cong S.Research on several quantum state estimation methods of quantum tomography[J].Journal of Systems Sciences and Mathematical Sciences,2014,34(12):1532-1546.
[23]李树涛,魏丹.压缩传感综述[J].自动化学报,2009,25(11):1369-1377.Li S T,Wei D.A survey on compressive sensing[J].Acta Automatica Sinica,2009,25(11):1369-1377.
[24]杨海蓉,张成,丁大为,等.压缩传感理论与重构算法[J].电子学报,2011,39(1):142-148.Yang H R,Zhang C,Ding D W,et al.The theory of compressed sensing and reconstruction algorithm[J].Acta Electronica Sinica,2011,39(1):142-148.
[25]李波,谢杰镇,王博亮.基于压缩传感理论的数据重建[J].计算机技术与发展,2009,19(5):23-29.Li B,Xie J Z,Wan B L.Signal reconstruction based on compressed sensing[J].Computer Technology and Development,2009,19(5):23-29.
[26]杨振亚,郑楚君.基于压缩传感的纯相位物体相位恢复[J].物理学报,2013,62(10):104203-1-104203-6.Yang Z Y,Zheng C J.Phase retrieval of pure phase object based on compressed sensing[J].Acta Physics Sinica,2013,62(10):104203-1-104203-6.
[27]丛爽,李克之.压缩传感理论及其在量子态估计中的应用[C]//第16届中国中国系统仿真技术及其应用年会.北京:中国系统工程学会,2015:307-311.Cong S,Li K Z.Compression sensing theory and its application in quantum state estimation[C]//Proceedings of 16th Chinese Conference on System Simulation Technology&Application(CCSSTA 2015).Beijing:System Engineering Society of China,2015:307-311.
[28]Recht B,Fazel M,Parrilo P A.Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[J].SIAM Review,2010,52(3):471-501.
[29]Candes E J,Plan Y.Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements[J].IEEE Transactions on Information Theory,2011,57(4):2342-2359.
[30]Liu Y K.Universal low-rank matrix recovery from Pauli measurements[C]//Advances in Neural Information Processing Systems.Berlin,Germnay:Springer,2011:1638-1646.
[31]Zheng K,Li K Z,Cong S.Characteristics optimization via compressed sensing in quantum state estimation[C]//Proceedings of the 2016 IEEE Multi-Conference on Systems and Control(MSC2016).Piscataway,NJ,USA:IEEE,2016:948-953.
[32]丛爽,张慧,李克之.基于压缩传感的量子状态估计算法的性能对比[J].模式识别与人工智能,2016,29(2):116-121.Cong S,Zhang H,Li K Z.Comparative study of quantum state estimation algorithm based on compressive sensing[J].Pattern Recognition and Artificial Intelligence,2016,29(2):116-121.
[33]Heinosaari T,Mazzarella L,Wolf M M.Quantum tomography under prior information[J].Communications in Mathematical Physics,2013,318(2):355-374.
[34]Liu W T,Zhang T,Liu J Y,et al.Experimental quantum state tomography via compressed sampling[J].Physical Review Letters,2012,108(17):170403.
[35]Baldwin C,Kalev A,Deutsch I.Quantum process estimation via compressed sensing with convex optimization[J].Bulletin of the American Physical Society,2014.
[36]Banaszek K,Cramer M,Gross D.Focus on quantum tomography[J].New Journal of Physics,2013,15(12):125020.