Analysis and Implementation of Highly Compressive Sensing

点击翻译按钮获取中文摘要

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.