稀疏恢复问题中精确恢复条件的研究

发布时间：2018-07-13 21:15

【摘要】：压缩感知作为Rn空间上的稀疏优化问题,旨在从被噪声污染或部分丢失的观测数据中恢复原始数据,在信号处理、图像去噪、医学成像等方面有着广泛的应用.近几年,压缩传感已经得到了深入的研究和快速的发展.随着现代信息技术的发展,需要存储、处理与分析的数据常常规模大、维度高、结构复杂,如人脸图像、监控视频、生物信息数据等.因此,本文着眼于压缩感知应用到复杂高维数据上而形成的稀疏优化问题,包括含有线性等式与不等式约束的稀疏解问题、低秩矩阵恢复问题、低秩张量恢复问题,使用压缩感知中的松弛逼近方法,解决NP-难的原问题.目前对于松弛问题的算法设计已经得到了学者们的广泛关注,但关于保证精确恢复的条件还没有很多的研究.本文对延伸的稀疏优化问题的精确恢复条件进行了系统的研究,并取得了如下成果:1.考虑绝对值方程组稀疏解的精确恢复条件,采用绝对值方程组与双线性规划的等价变形,在某种特殊情形下,求解绝对值方程组稀疏解的问题等价转化为含有线性等式与不等式约束的l0极小化问题.基于值域空间性质的分析,得到了该问题凸松弛的最优解存在唯一的条件,随后又证明了在此条件下,原问题与其凸松弛等价.根据这一研究方法与结果的启示,我们又围绕含有一般等式与不等式的线性约束的稀疏优化问题,讨论了这一问题的精确恢复条件,并通过一些例子验证了这一理论结果的正确性.2.讨论低秩矩阵恢复问题通过非凸的Schatten-p拟范数极小化问题精确恢复的条件,给出了保证成功恢复的一个p-RIP条件,并且证明了多少数目的观测值可以使得p-RIP条件以极高的概率被遇到.3.围绕低秩张量恢复问题,将低秩矩阵恢复问题中的三类精确恢复条件推广到张量空间中.之后,我们考虑一种同时包含无噪声和有噪声的低秩张量恢复模型,称为最小n-秩逼近,提出了求解该问题的一种迭代硬阈值算法,并且证明了该算法对于无噪声的情形在某些条件下以1/2的速率全局线性收敛,而对有噪声的情形迭代序列和真实值的距离是快速下降的.数值实验验证了这一理论结果,并且表明该算法对于求解低n-秩张量填充问题快速、有效.
[Abstract]:As a sparse optimization problem in rn space, compressed sensing is aimed at recovering raw data from noisy or partially lost observation data. It has been widely used in signal processing, image denoising, medical imaging and so on. In recent years, compression sensing has been deeply studied and developed rapidly. With the development of modern information technology, the data needed to be stored, processed and analyzed are often large scale, high dimension and complex structure, such as face image, surveillance video, biological information data and so on. Therefore, this paper focuses on sparse optimization problems resulting from the application of compressed sensing to complex high-dimensional data, including sparse solution problems with linear equality and inequality constraints, low-rank matrix restoration problems and low-rank Zhang Liang restoration problems. The relaxation approximation method in compressed sensing is used to solve the NP-hard problem. At present, the algorithm design of relaxation problem has been widely concerned by scholars, but there is not much research on the condition of guaranteeing accurate recovery. In this paper, the exact restoration conditions for the extended sparse optimization problem are systematically studied, and the following results are obtained: 1. Considering the exact restoration condition of sparse solutions of absolute value equations, the equivalent deformation of absolute value equations and bilinear programming is adopted. The problem of solving the sparse solutions of absolute value equations is equivalent to the l0 minimization problem with linear equality and inequality constraints. Based on the analysis of the properties of the range space, the existence and uniqueness conditions of the optimal solution for the convex relaxation of the problem are obtained, and then it is proved that the original problem is equivalent to its convex relaxation under this condition. According to the enlightenment of this research method and the results, we discuss the exact recovery condition of the problem around the sparse optimization problem with linear constraints of general equality and inequality. Some examples are given to verify the correctness of the theoretical results. 2. In this paper, we discuss the exact restoration condition of the low rank matrix restoration problem by non-convex Schatten-p quasi-norm minimization problem, and give a p-RIP condition to guarantee the successful recovery. It is also proved that the p-RIP condition can be encountered with a very high probability by the number of observations. In this paper, three kinds of exact restoration conditions for low rank Zhang Liang restoration problems are generalized to Zhang Liang spaces. Then we consider a low rank Zhang Liang restoration model with both noise-free and noise-free, which is called minimum n- rank approximation, and propose an iterative hard threshold algorithm for solving this problem. It is also proved that the algorithm converges globally linearly at a rate of 1 / 2 under certain conditions for noise-free cases, but the distance between the iterative sequence and the real value in the case of noise decreases rapidly. Numerical experiments verify the theoretical results and show that the algorithm is fast and effective for solving the low nrank Zhang Liang filling problem.
【学位授予单位】：天津大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP391.41

【相似文献】