Foundation and Reweighted Algorithms for Sparsest Points of Convex Sets with Application to Data Processing

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

Over the past a few years, the mathematical model for seeking sparsest solutions/points in a well-structured convex set has had a significant impact across disciplines. It becomes so important that seeking the sparsity has become a common request and task in such fields as signal recovery and denoising, image reconstruction and inpainting, face recognition, statistical estimation, pattern identification, model selection, machine learning, financial engineering, to name but a few. This, however, remains an emerging new area awaiting for urgent and extensive scientific research inputs. The proposed project aims to make significant UK contributions in this field, via providing sophisticated computational methods and related theory. The outcome of this proposed research will directly benefit to both academic and engineering communities. Up to now, the NP-hard sparsity-seeking model has been investigated dominantly by convex approximation method, i.e., l1-method. While it successfully solves a wide range of sparsity-seeking problems, it might fail in many situations as well. Reweighted methods have been numerically demonstrated being able to outperform the l1-method in many situations. However, the theoretical analysis for the reweighted algorithm is very limited so far, and many fundamental questions associated this method remain open. It is therefore imperative to develop a rigorous theory and efficient design for reweighted algorithms that, at present, lie at the research frontier of both applied mathematics and engineering. In this project, we aim at conducting a comprehensive and systematic study of such a theory and design, and to fully or partially address some important (open) questions in this field, and to apply the developed theory and algorithms timely to data processing, especially those from signal and image processing and financial problems. With a multidisciplinary character, the proposed research involves substantial exchange of ideas between applied mathematics (computational optimization and numerical analysis), engineering (sparse data representation and processing), and computer science (algorithmic design and complexity). We aim to achieve four closely related objectives. Successful completion one of these goals will bring useful ideas to achieve the next. First, we aim to enhance the existing theory and methods by developing new and relaxed conditions that guarantee the success of both weighted and non-weighted methods for locating sparsest points in convex sets. Second, we aim at developing a generic algorithmic framework and convergence theory for the general model of sparsity-seeking problems, leading to a new frontier in computational optimization, and stimulating more potential, complex applications in industrial sectors. Computer programs for research purpose (and possibly for commercial purpose later) will be compiled as well. Our third objective is largely to benefit academic communities by deeply exploring and deterministically justifying the interplay between reweighted and non-weighted algorithms. So far, this important research has not carried out yet in this field. Moreover, we aim for the deep relationship between the efficiency of reweighted algorithms and the concave minimization problem, leading to a new research frontier between the global optimization, fast data processing, and computational complexity.