Analysis and Implementation of Highly Compressive Sensing

该项目将研究压缩感知的性能极限，并提出接近这些性能极限的实用算法。该项目将集中在高压缩比区域，其中L1范数正则化是次优的。压缩感知将从统计物理的角度进行研究，并被视为自旋玻璃系统的一个特殊实例。平均失真和最小失真都将被作为目标函数(哈密顿量)来处理。分析将依赖于复制方法。该项目的主要目标是：1)找到一组鞍点方程来描述压缩传感问题的副本对称破缺解，2)将Guera的Sherrington-Kirkpatrick自旋玻璃模型的参数应用于压缩传感的自旋玻璃模型，从而证明这些解的严格的单边界，从而证明复制方法在压缩传感中的正确性，3)数值求解鞍点方程组，4)确定在高压缩比下哪些实用算法适用于压缩传感。

The project will investigate the performance limits of compressive sensing and propose practical algorithms that approach these performance limits closely.The project will focus on the regime of high compression ratios where L1-norm regularization is suboptimal.Compressive sensing will be investigated from the viewpoint of statistical physics and considered as a particular instance of a spin glass system.Both average distortion and minimax distortion will be addressed as objective functions (Hamiltonians).The analysis will rely on the replica method. Particular emphasis will be put on the implications of replica symmetry breaking.The main objectives of the project are:1) to find a system of saddle point equations that describe the replica symmetry breaking solution to the compressive sensing problem,2) to prove rigorous one-sided bounds for these solutions by adapting Guerra's arguments for the Sherrington-Kirkpatrick spin glass model to spin glass model of compressive sensing and, hereby, justifying the correctness of the replica method in compressive sensing,3) to numerically solve the system of saddle point equations, and 4) to determine which practical algorithms work well for compressive sensing at high compression ratios.