【作者】 陈娜；

【导师】 李红；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2012， 博士

【摘要】 压缩传感(Compressed Sensing)理论是在已知信号具有稀疏性或可压缩性的条件下,对信号数据进行采集、编解码的新理论.在压缩传感中,要恢复的目标是一个向量,而在很多实际问题中,例如图像修复、Netflix问题等等,待恢复的目标通常都是用矩阵来表示的,使得对数据的理解、建模、处理和分析更为方便.然而这些数据经常面临缺失、损失、受噪声污染等问题.如何在这种情形下得到准确的数据,就是矩阵恢复(Matrix Recovery)所要解决的问题.本文围绕矩阵恢复问题中模型的建立、算法的设计、误差分析这三个核心问题,对矩阵恢复问题的基本理论和主要方法进行了系统的阐述.首先,介绍矩阵恢复的研究背景、意义及研究现状.归纳已有的矩阵恢复模型及模型求解方法,总结其优缺点,在此基础上提出矩阵elastic-net正则化模型.其次,对矩阵elastic-net正则化模型的解及解的性质进行研究.构造算法对模型进行求解,并对算法的收敛性进行分析.另外,在不同的假设条件下分别讨论矩阵恢复模型的推广误差界.最后,给出矩阵恢复算法的一致β-稳定性条件,并通过实验验证算法的有效性及解的稳定性.论文的主要内容及结果如下：(1)低秩矩阵恢复问题中,通常的算法通过最小化矩阵核范数来达到低秩解,然而这些算法当数据的相关性非常强时通常会遇到不稳定的情况.论文通过在目标函数中加入矩阵的Frobenius范数,考虑矩阵elastic-net正则化模型,有效地解决了这种不稳定的问题.并且,利用凸优化中近邻算子的概念及相关性质推导出矩阵elastic-net正则化模型的解所满足的不动点方程,构造不动点迭代算法寻找模型的解,证明了迭代算法的解收敛到矩阵elastic-net正则化模型的解.(2)在矩阵RIP (Restricted Isometry Property)假设下分析矩阵elastic-net正则化模型的误差界.给出矩阵RIP假设的定义,及一些满足矩阵RIP的算子A的例子,证明了矩阵elastic-net正则化模型的误差界正比于噪声水平和矩阵自由度的乘积,并将结果推广到满秩矩阵的情形.(3)从统计学习理论的角度出发,在算子假设条件下,全面分析矩阵恢复算法的收敛性及推广性.将矩阵恢复问题描述成一个学习问题,定义一组Hilbert-Schmidt算子,利用算子逼近技术推导出矩阵elastic-net正则化模型的推广误差界,并给出一种自适应的正则化参数选取方法.(4)对算法的稳定性进行研究,考虑矩阵恢复算法的一致β-稳定性条件,给出了保证矩阵恢复算法一致β-稳定时,惩罚函数必需满足的条件.并且证明了本文中考虑的矩阵elastic-net正则化算法是一致β-稳定的.更多还原

【Abstract】 Compressed sensing is an emerging novel theory for data acquisition, encoding and de-coding under the specific assumption that the data is sparse or compressible. In compressed sensing, the object we wish to acquire is a vector, while in many application of practical inter-est, we often wish to reconstruct an object in the form of a matrix, which is more convenient for data acquisition, modeling, processing and analyzing. However, these data often suffer from the problem of deficiency, loss, or corrupted with noises. The goal of matrix recovery is to acquire the exact data under these situations.In this thesis, we systematically review the basic theory and main methods of matrix recovery around the three core problem of modeling, algorithm designing, and error analysis. First, we present a quick overview of backgrounds, significance and research status of matrix recovery. The mathematic models and assumptions for matrix recovery are provided. We in-troduce the methods for solving these models, summarize the advantages and disadvantages of the methods, and then propose an elastic-net regularization model for matrix recovery. Second, the solution of the matrix elastic-net regularization model and the properties of the solution are discussed. We construct an iterative algorithm for solving the model, and pro-vide a convergence analysis of the algorithm. Moreover, we analyze the generalization error bounds of matrix elastic-net regularization under different assumptions. Finally, we char-acterize the conditions on the penalty function that lead to uniformβ-stability and present numerical experiments to illustrate the effectiveness and the stability of the algorithm.The main results of the thesis could be summarized as follows:(1) In the problem of low-rank matrix recovery, traditional algorithms obtain low-rank solutions by minimizing the nuclear norm of the matrix. However, the algorithms are unsta-ble when the data matrix is highly correlated. Therefore, we consider the matrix elastic-net regularization, which can lead to stable solutions by minimizing the empirical risk penalized with the combination of the nuclear norm and the Frobenius norm. Moreover, the solution of the model can be characterized as the fixed point of a contractive map by the proximity oper- ator. Then we construct a fixed point iterative scheme for solving the model. The theoretical results show that the sequence of iterates converges to the solution of the matrix elastic-net regularization.(2) The error bounds of the matrix elastic-net regularization model under the assumption of matrix restricted isometry property (RIP) are analyzed. We give the definition of the RIP for matrix recovery, and show that certain classes of random measurements satisfy the matrix RIP. The analysis indicates that the error is proportional to the number of degrees of freedom times the noise level under the matrix RIP. Error bound is also established for full-rank matrices.(3) In the framework of statistical learning theory, we give an all-round analysis on the convergence and the generalization performance of the matrix recovery algorithms under the operator assumptions. We describe the matrix recovery problem as a learning problem, and define some Hilbert-Schmidt operators. The generalization error bounds for matrix recovery are then obtained by estimates of Hilbert-Schmidt operators. It is worth mentioning that we also give an adaptive scheme to select the regularization parameter.(4) The stability of the matrix recovery algorithms is studied. We consider the uniformβ-stability of matrix recovery algorithms and characterize the conditions on the penalty function that lead to uniformβ-stability. In particular, we apply our results to show that the matrix elastic-net regularization is uniformlyβ-stable.更多还原