文章快速检索  
  高级检索
压缩传感理论、优化算法及其在系统状态重构中应用
丛爽, 张娇娇    
中国科学技术大学信息科学技术学院, 安徽 合肥 230027
摘要: 分别对压缩传感理论、优化算法及其在系统状态重构中的应用3个方面进行了研究.在压缩传感理论方面,包括对所压缩信号的稀疏或低秩要求、编码测量以及与优化算法之间的关系进行了较为深入的研究,重点分析了原始信号的稀疏与低秩之间的关系、测量矩阵与压缩矩阵之间的关系、满足限制等距特性(RIP)的测量矩阵,以及由压缩传感理论提供的最少测量次数.在压缩信号重构过程中所需要采用的优化算法,着重讨论了核函数的凸优化问题描述,分别对常用的优化算法,包括最小二乘(LS)法、最大熵法、极大似然法和贝叶斯方法的求解过程中所用到的性能指标、优化目标和求解条件等进行了归纳与特性分析.对量子态估计中的交替方向乘子法(ADMM)以及作者最新提出的迭代阈值收缩法(IST)进行了专门的性能对比,并通过量子位分别5、6和7情况下纯态估计的应用为例,对不同测量比率对参数估计性能的影响,以及算法在不同量子位数下性能的表现,进行了不同层次上的对比和分析,完整地阐述基于压缩传感理论与优化的系统参数估计的研究过程.
关键词: 压缩传感理论     测量比率     最小二乘算法     交替方向乘子法     迭代阈值收缩法     密度矩阵重构    
Compressive Sensing Theory, Optimization Algorithm and Application in System State Reconstruction
CONG Shuang, ZHANG Jiaojiao    
Department of Automation, University of Science and Technology of China, Hefei 230027, China
Abstract: 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.
Key words: compressive sensing (CS) theroey     measurement rate     least square algorithm     alternating direction multiplier method (ADMM)     iterative shrinkage-thresholding (IST)     density matrix reconstruction    

1 引言

压缩传感(compressive sensing)理论是对稀疏信号数据同时进行采样、压缩和恢复的理论,该理论将嵌在高维空间中的输入信号,变换成维数较小空间中的信号,并在获取信号的同时对数据进行适当的压缩,然后再利用合适的重建算法,对压缩的数据进行信号恢复[1]. 2006年Candes和Donoho等人提出[2-3]:信号只要在某种变换基下是稀疏的,那么就可以通过设计一种压缩矩阵,将高维信号投影到一个低维空间上;在压缩矩阵与变换基满足不相关的前提下,通过解决一个最优化问题来重构被压缩的稀疏信号.在压缩传感理论框架下,采样速率不再取决于信号的带宽,在很大程度上取决于两个基本准则:信号的稀疏结构和测量矩阵的不相关性[4].一般而言,在压缩传感理论中要恢复的目标是一个向量,不过在一些实际问题中,例如图像修复、Netflix问题、量子态估计等实际应用中,待恢复的目标往往是一个矩阵,对于这些数据面临缺失、损失、受噪声污染等问题,如何能够获得准确的原始矩阵,就是矩阵恢复问题,此时基于压缩传感理论,利用的是矩阵奇异值的稀疏性,也就是矩阵的低秩性来恢复原始矩阵[5].

在目前基于压缩传感的应用中,量子系统状态估计的应用引起人们的极大兴趣,因为一个n量子位的量子状态,需要采用希尔伯特空间的d×d维的密度矩阵ρ来描述[6],其中d=2n,所要估计的量子态参数及其测量数目d×d是随着n的增长呈指数增加:一个标准的量子态估计需要d×d=2n×2n=4n次测量配置[7-8].人们希望基于压缩传感理论来解决测量配置随量子位数的增加而指数增长的问题,尤其是当量子态是纯态或者近似纯态时,状态密度矩阵ρ是一个低秩的厄米矩阵,具备奇异值稀疏的特性,采用压缩传感的方法,完全可以通过较少的测量次数精确地重构出ρ[9-11].在系统参数估计中,压缩传感理论解决的是减少测量次数的问题,高精度参数估计的实现还需要用到优化算法[12].已经开发出的优化算法有:最小二乘法[13]、贝叶斯法、交替方向乘子法[14]等,其中,交替方向乘子法,简称ADMM,是一种求解具有可分结构的凸优化问题的重要方法,其最早由Gabay和Mercier于1967年提出[15]. ADMM是结合对偶上升法的可分离特性以及ALM松弛收敛条件所形成的一种改进方法[16],该算法在大规模数据分析处理领域因处理速度快,收敛性能好而备受关注. Yuan和Yang将ADMM用于求解核范数最小化问题[17];Yang和Zhang将ADMM算法用于求解基于压缩传感的范数最小化问题[18],证明了ADMM重构稀疏矩阵的有效性;Li[14]首次将ADMM用于基于压缩感传的量子态重构,解决了同时包含核范数和范数的优化问题.近些年来关于基于压缩传感的凸优化问题求解方法被广泛研究,这些问题主要围绕带有约束的范数或核范数最小化.对于范数最小化,包括内点法(interior point,IP)[19]和梯度投影法(gradient projection)[20],以及用于量子态估计的迭代阈值收缩法(iterative shrinkage-thresholding algorithm,IST)与ADMM结合的改进算法[21]等.最近几年里,国内研究人员在压缩传感理论、重构算法以及在数据重建、医学图像压缩与重构、纯相位物体相位恢复等方面都进行了较广泛的综述和研究[22-26].

基于压缩传感理论的应用离不开优化算法,并且压缩传感理论、优化算法及其应用这3个方面隶属不同的研究领域:压缩传感理论是通讯中的信号处理;优化算法是计算机科学中的一个研究方向;如果想做好某一个基于压缩传感理论的应用,就必须对所涉及到的3个方面的内容都比较精通,这对人们提出了较高的要求,一般需要一定的时间来熟悉3个领域中的研究成果,并且还要能够很好地结合在一起.本文希望在对压缩传感理论及优化算法进行系统性地阐述的基础上,结合在量子态估计中应用的实例,充分展现压缩传感理论的内容和功效、所能完成的任务、与优化算法之间的关系,各种优化算法及其相互之间在性能上的差异,以及基于压缩传感理论及优化算法在量子态估计中的优越性.

2 压缩传感理论

压缩传感理论主要包括3个方面[27]:信号的稀疏表示,编码测量和重建算法.

压缩传感理论可以实现的充分条件为:信号必须是稀疏的或经过变换后是稀疏向量.若一个信号绝大部分元素为零,只存在少数非零元素,则称该信号是稀疏的.若信号本身不是稀疏信号,当采用某种变换基对信号进行变换后得到的系数中绝大部分的绝对值很小,此时得到的就是稀疏的或近似稀疏的变换向量.设X是一个一维实值、长度为N的离散时域信号,X可以看作是一个在RN空间中N×1的列向量,并且可以通过某组正交基Ψ=[ψ1 ψ2 … ψn]表示为

(1)

其中,si= < XΨi >是投影系数,构成一个N×1的列向量信号. XS代表的是同一个信号:X是在时域中的信号,而S是在Ψ域中的信号.

矩阵的稀疏表示严格而言可以分为两种:矩阵元素的稀疏性,即矩阵非0元素的个数相对较少和矩阵奇异值的稀疏性,即矩阵奇异值非0的个数较少,矩阵的秩相对较小.

编码测量是压缩传感理论另一个核心部分,它是信号由高维转化为低维的过程.人们对所获取的N×1维信号数据X,通过某种变换压缩,将数据量N×1压缩为数据M,这里有M«N.人们利用M次线性采样,通过计算信号X和一个M×N维的测量矩阵Φ的左乘,来获得对信号X压缩后M个编码测量的输出值YY=ΦX,其中,Y是一个M×1的向量,Φ中每一行可以看作是一个传感器,传感过程中与信号X相乘,获取信号X中的一部分信息.

压缩传感理论通过选择某组正交基Ψ将原始信号X稀疏化为S,或通过选择一个测量矩阵Φ,来对稀疏的信号S进行部分数据的测量,获得信号X压缩后M个编码测量的输出值Y

(2)

其中,Θ=ΦΨ是一个M×N的传感矩阵.

压缩传感的关键部分是编码端的测量矩阵Φ必须与信号的稀疏变换基矩阵Ψ具有不相关性,且Φ的选择满足随机性.对于测量矩阵Φ的选取,目前大部分情况下都采用满足高斯分布的白噪声矩阵、伯努利分布的±1矩阵、傅里叶随机测量矩阵、非相关测量矩阵等,因为这些矩阵的分布都具有很强的随机性,能够保证和多数正交变换基Ψ有很大的不相关性.在编码测量输出值的获取过程中,与传统直接采样信号不同,压缩传感获取的是目标信号的线性测量Y=ΦX.由信号XS之间的关系(1):X=ΨS,可以得到YS之间的关系:Y=ΘS,其中传感矩阵Θ=ΦΨ同样为一个M×N矩阵.

信号重构是根据压缩传感后的信号Y,将其原信号X恢复出来的过程.此过程可描述为:在通过模拟信息转换过程获取得到数字信号Y(M×1) 之后,通过设计出合适的测量矩阵Φ,结合适当的重建算法,实现对原数字信号X(N×1) 的重建,或者通过Θ=ΦΨ来恢复信号S.为此人们需要建立一个基于测量矩阵的数据获取体系:对长为N的信号X,或者是X在域Ψ中的稀疏系数向量S进行M次测量.对于压缩传感信号重建问题,理想情况下是希望通过求解范数问题来得到X,但由于范数的优化问题实际上是NP-hard组合问题,难以求解或者无法验证解的可靠性,于是将范数变换成范数.事实上这个范数问题是一个凸优化问题,能通过数学上许多经典的优化技巧被有效地解决.另外,由于核范数是凸的,最小化核范数的优化问题就变为一个凸优化问题,因此必有唯一最优解.如果这种近似可以接受,那么这个问题自然也就解决了.最近的研究表明:尽管在最坏的情况下,最小化诸如稀疏性或矩阵秩这样的目标函数是NP难题,但是在某些合理的假设条件下,通过优化目标函数的凸松弛替代函数,采用凸优化方法,可以精确地解出问题的最优解.而且随着维数的增加,这种成功的概率会迅速地趋于1.相关的理论研究、算法设计和应用都正在不断的展开.目前压缩传感领域的研究工作主要集中在理论层面,Candes、Tao、Donoho等人已经成功构建了压缩传感的理论框架,给出测量矩阵Φ需满足的充分条件,即一致不确定性原理;传感矩阵的行数M与信号稀疏度k之间必须满足Mkln(N)的关系等.除此之外,也有许多关于解决该理论中具体问题的研究成果,主要集中在测量矩阵Φ与重建算法两个方面.

在压缩传感中,信号的表达是局部化的,每一次测量都包含一小部分信号分量的信息.这样测量之所以有效,依赖于信号在基表达下的稀疏性和测量之间的一致不确定原理.一般情况下,并不是所有的低秩矩阵都可以被恢复,矩阵恢复不仅对矩阵本身有要求,对采样数目及采样方式都有一定的要求.在编码测量中,所选择的测量矩阵Φ需要满足RIP条件. RIP意思为限制等距特性(restricted isometry property),又称之为一致不确定原理(uniform uncertainty principle,UUP).等价的说法是:所有测量矩阵Φ对应的S列向量近似正交.所以应用好压缩传感理论的关键在于选择好的测量矩阵Φ或者传感矩阵Θ.

基于压缩传感理论,若可以将原始信号进行稀疏表示,或原始信号为低秩信号,那么在满足矩阵可恢复的秩RIP假设前提下对原始信号进行编码测量,压缩传感理论提供了需要恢复原始信号的最少测量次数.人们可以根据压缩传感理论提供的最小采样率来进行测量次数的设计.以量子态估计为例,采用量子层析所需要的完备测量次数为d2,测量比率(或压缩比率)的定义为:η=M/d2η越小,表示压缩比越大,所需要测量次数M越少.所以压缩传感理论中的一个重要研究方向就是满足RIP条件的测量矩阵的设计及其最小测量次数M的研究.到目前为止,已经研究出能很好地满足RIP条件的测量矩阵有具有近似等距(nearly isometric)分布的高斯(Gaussian)随机矩阵和贝努利(Bernoulli)矩阵,另外,哈达码矩阵和贝叶斯(Bayesian)矩阵也能很好地满足RIP条件.此时,压缩传感理论给出了相应的最少测量次数.以秩为r的量子纯态密度矩阵重构为例,现有的压缩传感理论的研究成果有:

1) Recht等人的研究成果表明[28]:若测量矩阵为近似等距分布的随机矩阵,对于任意的δ∈(0,1),存在正常数c0,当测量数目满足

(3)

时,则测量矩阵以趋于1的概率满足RIP,概率值大小为:P≥1-exp(c1·M),其中c0c1为仅由δ决定的正常数.

2) Candes等人的研究结果表明[29]:若测量矩阵为高斯测量集合时,对于任意的δ∈(0,1),存在正常数D,当测量数目M满足

(4)

时,则测量矩阵以趋近1的概率满足RIP,概率值大小为:P≥1-c·exp(-d·M).

3) Liu已经证明[30]:当测量数目M满足

(5)

时,由泡利矩阵构成的测量矩阵以趋于1的概率满足RIP,此时,原始信号重构问题能够都能够以趋于1的概率到达唯一最优解且等于密度矩阵.

式(3)、式(4) 和式(5) 表明:采用不同的测量矩阵,所需要的测量次数是不同的,所获得的测量结果的性能也是不同的,需要注意的是这其中还存在一个测量矩阵的可实现问题.在量子纯态估计应用中的研究已经表明[31]:测量矩阵采用高斯随机矩阵、近似等距分布和贝努利矩阵等,都比由泡利(Pauli)矩阵构成的测量矩阵的状态估计性能要好.不过,由于这些理论上给出的好的测量矩阵很难在实际实验装置上实现,因此目前在实际应用中,主要还是采用由泡利矩阵构成的测量矩阵.

压缩传感理论告诉人们能够恢复出低秩原始信号X需要的最少测量次数M.由于M远远小于所需要的测量总数,必须采用重构优化算法才能够近似估计出原始信号.换句话说,压缩传感理论只是解决了能够估计出参数的最少采样次数,如何估计出原始信号参数的方法,以及实际估计出参数性能的好坏,则取决于所采用的具体重构算法.效率不好的算法,估计出参数的精度也不会高.所以,用于参数重构的优化算法也是目前一个人们热门研究的内容.

3 信号重构的优化算法

压缩传感理论提供的最少测量次数从理论上保证可以从测量结果Y中恢复稀疏可压缩的信号X,但它并没有告诉人们应该如何去恢复信号X,这是压缩传感的第二个需要解决的问题:信号重构或解码过程.此问题可以这样描述:已知测量结果Y,随机测量矩阵Φ和基矩阵Ψ,通过求解方程(2) 来解出长度为N的信号X或稀疏域中向量S.

从数学上讲,从选择到的不完整的压缩测量矩阵Φ∈RM×N,恢复出完整的低秩矩阵X的优化问题可以表示为一个核函数的凸优化问题:

(6)

其中,‖·‖*为矩阵的核范数,为矩阵奇异值的和: rX的秩,σi(X)为矩阵Xi大的奇异值.

基于压缩传感理论中的压缩测量矩阵所建立的优化问题(6) 实际上是一个带有约束条件的核函数的凸优化问题.这个约束条件为由压缩传感获取原信号的线性测量关系.此时,可以通过引入拉格朗日函数,将问题转变为一个无约束的和有可分结构凸优化问题:对于一个以x∈Rn为自变量的目标函数f(x),另一个以z∈Rm为自变量的目标函数g(z),fg为凸函数,在xz满足线性约束下的优化问题为

(7)

其中,A∈Rp×nB∈Rp×mc∈Rp.

重构算法一般需要满足以下5个条件:1) 算法能适用于各种不同的采样方式;2) 算法能保证解码端重构出原始信号的误差是最优的;3) 算法能在加入噪声的实际应用情形下具有高度的鲁棒性;4) 算法能在最少采样点情况下精确地重构出原始信号;5) 算法具有很好的效率,运算复杂度越低越好.现有的重构算法几乎都没有同时满足以上所有的条件,一般都只是在它们之间有所取舍而做个平衡.

常用的优化算法有:最小二乘(LS)法、最大熵法、极大似然法和贝叶斯方法[22],只是各自都有其适用条件.

最小二乘估计方法可以在测量次数有限时,通过使得测量数据与实际数据之间误差的平方和为最小情况下,将相对独立的参数放到同一个约束下,得到总体上的最优结果.最小二乘估计是利用系统的输入输出数据{u(t)}和{y(t)},通过使性能指标函数:

(8)

取最小值,来获得参数矢量θ的估计,记做,其中称为参数θ的最小二乘估计值.对(8) 式中θ求偏导,并令之为0,可以得到最小二乘估计结果为

(9)

最大熵算法是利用最大熵原理对随机事件的概率分布进行推断的方法.在已知部分信息的前提下,最大熵估计方法能够对概率进行推断,并保证推断结果的随机不确定性最大.考虑某随机事件,其概率分布为p={p1p2,…,pn},概率分布满足约束条件:

(10)

其中,pi=p(X=xi)(i=1,2,…,n),xi表示分布的第i种事件结果,gr(xi)表示结果xi对应的函数值,r=1,2,…,m表示共有m种不同函数,ar为在第r种函数下概率分布的期望值.

假设pi为测量得到的结果,希望得到随机概率分布的最佳估计,取概率分布的熵作为目标函数:

(11)

其中,熵值Hp代表了此分布的不确定程度. Hp为0时,表示此分布是确定的,结果只有一种;Hp的值越大,代表分布的不确定性越大,也就越接近真实情况.因此,令目标函数(11) 取得极大值时的概率分布,即为最佳估计.

最大熵法适用于不完全测量情况下参数的估计,它的前提是必须能对给定可观察的期望值或概率分布进行准确的测量.为了得到那些需要的期望值,一般需要测量次数足够得多.最大熵法的优点在于,对不完全测量情况能够得到最接近真实值的无偏状态估计;缺点是拉格朗日乘子的方程组不一定有解,有时会出现无解的情况.

极大似然算法是通过选取目标函数为似然函数,在未知参数的可能取值范围内,求解似然函数的最大值情况下的参数值来作为未知参数的估计值.设某离散型随机变量X,其概率函数为p(xθ),其中θ是未知参数.设X1X2,…,Xm为取自总体X的样本,若已知实验结果是x1x2,…,xm,则事件{X1=x1X2=x2,…,Xm=xm}发生的概率为,这一概率值随θ的值的变化而变化.由实验结果可以对参数θ进行估计,利用极大似然原理构建出的目标函数形式为

(12)

其中,L(θ)称为似然函数,参数θ为变量.

极大似然估计法是在参数θ的可能取值范围内,选取使(12) 式达到最大的参数值来作为参数θ的估计值.所以,极大似然法的核心是构造似然函数,它在不完全测量情况下也能够得到状态的最佳推断,其缺点是估计过程中要涉及到非常复杂的计算,虽然可以采用数值计算方法进行迭代计算,但计算过程依然复杂.同样是用部分信息推断系统状态,极大似然法与最大熵法的不同点为:极大似然法选择最可能的推断,而最大熵法是由已知信息得到无偏的估计结果.

贝叶斯估计方法是应用贝叶斯理论对事件的概率进行统计推断的一种方法.在推断过程中,不仅需要用到测量结果,还需要用到人们对推断对象的提前认知.贝叶斯估计方法的原理为:对于不独立的事件AB,若已知事件A发生的概率为P(A)(称为先验概率,或无条件概率),则在事件A发生的前提下,事件B发生的概率称为BA的后验概率(也称条件概率),记为P(B|A).那么可以得到事件AB同时发生的概率为P(AB)=P(B|A)P(A),由此便可以推断事件B发生的条件下,事件A发生的概率为

(13)

式(13) 被称为贝叶斯公式,它是贝叶斯原理的核心.假设有一些列互不相容事件A1A2,…,An,并满足=Ω(i=1,2,…,n),其中Ω为事件空间,且P(Ω)=1,对于任意Ai,先验P(Ai)已知,测得任意Ai发生的前提下B发生的概率P(B|Ai),使用贝叶斯方法可以对Ai的条件概率进行重新估计为

(14)

这样,在不知道事件B发生概率的情况下,人们通过测量B的后验概率,就能得到对所有Ai后验概率的估计,这就是贝叶斯估计.人们在已知任意Ai先验概率的条件下,通过测量获得样本,从而对先验概率进行调整,调整方法就是通过贝叶斯估计公式,调整结果就是后验概率P(Ai|B).因此,贝叶斯估计可以看成一个信息收集过程,通过测量不断更新所要估计的对象.

在以上4种参数估计算法中,最小二乘法本质上是对误差进行最小化情况下对参数的估计.相比极大似然与最大熵法,最小二乘法所得到估计结果的近似度更高,需要的计算量最小.最大熵法与极大似然法均能在只获得部分可观测量的情况下,对状态进行有效估计,其中最大熵法为无偏估计,极大似然法更注重“最大可能的结果”.贝叶斯方法的特点是估计过程中需要对先验信息的使用.对于不同的先验信息,往往会得到不同估计结果;在测量不完全,或者无法准确得到被观察量的平均值时,依然能够获得有效的估计结果.

当把这些常用的优化算法应用到较复杂的参数重构的问题中,比如,待估计的参数值是以指数增长的量子系统密度矩阵时,重构效果就显得逊色,尤其当量子位数比较大时,无论从重构所花费的时间还是性能上都不尽如人意,所以需要开发出效率更好的优化算法.最近几年,在量子态估计方面研发出的交替方向乘子法(ADMM)算法及其改进算法[14, 21].

对于式(6) 的优化求解问题,ADMM的思想就是全局问题(6) 分解为两个较小、较容易求解的子问题,利用两个目标函数f(x)和g(z),通过分别对其变量xz的交替更新,来得到问题(6) 的最优解,迭代公式为

从迭代公式(15) 中可以看出:ADMM将大的全局问题(6) 分解为两个较小、较容易求解的子问题(15a)、(15b),并通过协调子问题的解而得到全局问题的解.不过,ADMM只是一种求解优化问题的计算框架,每一个子问题(15a)和(15b)如何有效求解,需要根据f(x)和g(z)具体形式来确定.

在实际系统的测量中,常常存在干扰.当考虑稀疏的干扰矩阵S时,此时的待优化的函数中同时包含光滑和非光滑函数.研究结果表明:迭代阈值收缩法(IST)可以很好地解决目标函数中含有非光滑项的核凸优化问题. IST的每一次迭代都由光滑函数f(x)的梯度下降操作和非光滑函数g(x)的近邻算子操作两部分构成,其中梯度下降的步长tk的选择对算法的收敛性和收敛速度至关重要. IST-ADMM的迭代公式为

(16)

与ADMM算法[14]相比,IST-ADMM的迭代求解过程不需要计算M×d2的矩阵A的伪逆(A*A)-1A*,这涉及到d2×d2的矩阵求逆以及d2×d2d2×M矩阵相乘,计算复杂度为O(d6);而是通过IST梯度下降和近邻算子操作得到ADMM子问题的解,再代入ADMM迭代框架得到全局问题的解,运算过程涉及最大的计算量为M×d2的矩阵Ad2×1的向量相乘,计算复杂度为O(M·d2),因此IST-ADMM算法可以大幅度减少计算时间和存储空间.

在系统参数重构的应用中,由于测量噪声和优化算法等因素的影响,为了达到希望的重构精度,一般都要采用大于压缩传感给出的理论测量次数.一个优化算法的性能越好,就越能够以接近压缩传感理论给出的测量次数,达到期望的参数重构精度.

4 基于压缩传感理论与优化算法的量子态估计应用实例

量子态估计是一个典型的受益于压缩传感理论与优化算法的应用领域.基于压缩传感的量子估计算法[32-33]融合了控制理论和信号处理两方面内容[34-36].由于量子状态无法通过测量直接确定,必须通过对量子态的投影测量,对量子态重构来估计出量子态的密度矩阵.量子层析是确定未知量子系统状态的常用方法,是通过求解概率值逆变换求解出密度矩阵的过程,它需要使用d2次测量结果.所以采用量子层析进行量子态估计的一个基本困难是测量次数随量子位数的增加而指数增涨.例如,一个6比特量子态的层析,需要26×26=4 096次测量;一个7比特量子态的测量次数是47=16 384.测量次数4n是随着比特n的增加呈指数增加.另外,为了获得高精度的估计结果,每一个测量都需要重复很多次.在采用压缩传感理论之前,一个实验中量子态的测量及其获得是一件极其耗时的事情,一般仅适用于2和3比特量子系统.本节将以基于压缩传感理论与优化算法的量子态估计为实例,完整地展现压缩传感理论和优化算法在具体的量子态估计中所显示出的性能与效果.

对于一个由密度矩阵ρCd×d描述的n为量子系统,其秩为rank(ρ)=r,量子态估计的任务就是如何根据所获得的观测值重构出密度矩阵ρ.定义一组正交基Ψ构成的观测矩阵O=[O1 O2 … Od2],从这d2个观测矩阵中随机选取Mo1,…,oMoi∈Cd×d,组成测量矩阵Φ∈CM×d2Φ的第i行是由观测矩阵oi按行连接得到,所对应的观测值为:yi=c·tr(oi*ρ)或y=Φvec(ρ)+e.正交基的选择是不唯一的.当正交基选为泡利矩阵{1 σx σy σz}时,观测矩阵Ο*

(17)

其中,σi1σi2,…,σin的下标i1,i2,…,in分别取值0、1、2、3.观测矩阵还可以表示为:Ο*={oi}d2i=1,其中oi为观测矩阵Ο*的第i行的元素.

由于待恢复的密度矩阵ρd×d维的,通常需要O(d2)次测量.当量子系统是纯态或者近似纯态时,密度矩阵ρ是低秩的,即r«d,奇异值具备稀疏性.在实际系统的测量中常常存在干扰,考虑稀疏的干扰矩阵S,则带有干扰的量子状态估计问题可以转变为一个对密度矩阵和干扰的双目标优化问题[20]

(18)

其中,ρ∈Cd×dS∈Cd×dΦ∈CM×d2M«d2,‖·‖*为核范数,‖ρ*=siρ的奇异值,vec(·)表示将矩阵按列展成一个列向量. ‖·‖1表示范数,定义为IC(ρ)为示性函数,定义为:IC(ρ)=∞示性函数IC(ρ)的作用是把矩阵投影为厄米矩阵,γ为参数,代表干扰项所占的权重.

最少测量次数M可以由压缩传感理论提供的式(5) 或式(3) 来确定.

研究成果表明:对于非常少的数据,不需要对本征态甚至低秩有任何事先的假设,就可以重构出低秩量子状态.目前压缩传感理论的研究重点主要集中在随机选取最少的M个数、恢复出解的误差界的大小,以及算法的计算复杂度的减少上.在量子态估计应用方面的研究重点在高效快速的优化算法上,不同的优化算法在状态重构精度上的差别很大,尤其在对高量子位的状态估计中所显示出得效率尤为突出.为了更加清楚地展现这两个特点,下面给出两个量子状态估计的实例.

分别采用LS和ADMM两种优化算法,在无和有干扰的情况下,对n=6的量子系统进行状态估计进行了性能对比研究,实验结果如图 1所示[32].实验的目的主要是考查测量比率分别从0.1到0.5递增的过程中,不同算法的估计误差的大小.实验中所添加的干扰,其个数为密度矩阵ρ元素个数的10%,即为0.1d2个干扰,干扰幅度满足高斯分布N(0,0.1‖ρF).从图 1中可以看出:不论是否有干扰,采用LS算法进行估计,其效果都不是很好:直到测量比率到达50%,状态重构的归一化误差只达到0.5,表明有一半情况下的估计都是错误的.而当采用ADMM算法时,当测量比率值需要用到总测量数据的20%时,状态重构的归一化误差在无干扰情况下达到了0.008 7,有干扰情况下的状态估计误差达到0.364.这说明ADMM算法在无干扰情况下的状态估计效果要比LS好很多,不过存在干扰时的状态估计精度有待进一步提高.

图 1 无和有干扰下两种算法的状态估计实验结果 Figure 1 Experimental results of state estimation in the cases of with and without disturbance under two algorithms

基于压缩传感理论进行系统状态估计的另一个优势是:随着指数位数的增加,所需要的测量比率也随之下降.此特性在具有指数增长参数的高量子位状态估计中尤其明显,显示出压缩传感理论在量子态估计中的重要性.

第2个应用实例是分别采用IST-ADMM和ADMM算法,在有干扰的情况下,分别对量子位为n=5,6,7量子态的估计的实验,实验结果如图 2所示,从中可以看出:不论哪种算法,达到相同误差所需要的测量率,都是随着量子位数的增加而减小;换句话说,在相同测量率下,状态重构正确率是随着量子位数的增加而增加,比如,在测量率为0.15,量子位分别为5,6和7时,IST-ADMM算法重构的正确率分别为98.71%,99.39%和99.30%;此时ADMM重构的正确率分别为34.10%,47.76%和59.56%.

图 2 IST-ADMM与ADMM算法归一化状态重构误差 Figure 2 Normalized reconstruction error of IST-ADMM and ADMM

另外,IST_ADMM算法在计算时间上也展现出明显的优势.为了更加清楚地考察IST-ADMM算法计算速度的优越性,表 1给出量子位n=5,6,7,测量比率η=0.1,0.25,0.4时,IST-ADMM算法和ADMM算法执行30次迭代所需要的时间.从表 1中可以看出:以测量比率为0.25,算法执行30次迭代所需要的时间为例:n=5时,ADMM算法花费的重构时间是16.36 s,而IST-ADMM算法只需要0.13 s,当n=7时,IST-ADMM算法也只需要1.63 s,只是ADMM算法的9 047.76 s的5 551分之一的时间.这种快速优化算法与压缩传感理论结合的量子状态估计的应用,向着可实现的实际应用方向迈近了一大步.

表 1 IST_ADMM算法与ADMM算法重构时间(秒) Table 1 Reconstruction time of IST_ADMM and ADMM algorithm (s)
5 结论

本文将压缩传感理论和与其紧密相关的优化算法以及在系统参数估计应用中所涉及的关键理论、术语及其相互关系和具体应用有机地联系起来,进行统一的阐述与具体的应用,并通过实例展现了压缩传感理论及高效快速优化算法在量子态估计应用所显示出来的优越性和非凡效果.研究结果表明:借助于压缩传感理论,可以极大地减少系统参数估计中所需要的测量次数;测量比率值是随着指数值的增加而大幅度减少;高效快速的优化算法能够对指数增长的复杂系统的参数估计,提供有效可实现的参数估计技术方法和手段,具有重要的实际应用价值.

参考文献
[1] Candes E, Romberg J. Sparsity and incoherence in compressive sampling[J]. Inverse Problems, 2007, 23(3): 969–985. DOI:10.1088/0266-5611/23/3/008
[2] Candes E J, Tao T. Decoding by linear programming[J]. IEEE Transactions on Information Theory, 2005, 51(12): 4203–4215. DOI:10.1109/TIT.2005.858979
[3] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289–1306. DOI:10.1109/TIT.2006.871582
[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. DOI:10.1103/PhysRevLett.111.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. DOI:10.1088/1367-2630/14/9/095022
[7] Lloyd S, Mohseni M, Rebentrost P. Quantum principal component analysis[J]. Nature Physics, 2014, 10(9): 631–633. DOI:10.1038/nphys3029
[8] Ferrie C. Self-guided quantum tomography[J]. Physical review letters, 2014, 113(19): 190404. DOI:10.1103/PhysRevLett.113.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. DOI:10.1103/PhysRevLett.105.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. DOI:10.1103/PhysRevLett.106.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. DOI:10.1103/PhysRevLett.108.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. DOI:10.1103/PhysRevA.87.030102
[13] Qi B, Hou Z, Li L, et al. Quantum state tomography via linear regression estimation[J]. Scientific Reports, 2013, 3: 3496. DOI:10.1038/srep03496
[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 -problems in compressive sensing[J]. SIAM Journal on Scientific Computing, 2011, 33(1): 250–278. DOI:10.1137/090777761
[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. DOI:10.1109/JSTSP.2007.910281
[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.
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. DOI:10.7498/aps.62.104203
[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. DOI:10.1137/070697835
[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. DOI:10.1109/TIT.2011.2111771
[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. DOI:10.1007/s00220-013-1671-8
[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. DOI:10.1103/PhysRevLett.108.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. DOI:10.1088/1367-2630/15/12/125020
http://dx.doi.org/10.13976/j.cnki.xk.2017.0267
中国科学院主管,中国科学院沈阳自动化研究所、中国自动化学会共同主办。
0

文章信息

丛爽,张娇娇
CONG Shuang, ZHANG Jiaojiao
压缩传感理论、优化算法及其在系统状态重构中应用
Compressive Sensing Theory, Optimization Algorithm and Application in System State Reconstruction
信息与控制, 2017, 46(3): 267-274.
Information and Control, 2017, 46(3): 267-274.
http://dx.doi.org/10.13976/j.cnki.xk.2017.0267

文章历史

收稿/录用/修回: 2016-10-31/2017-04-14/2017-04-18

工作空间