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.

The development of efficient mathematical methods and related theory for a central problem lying at the research frontier of science and engineering will always have direct and indirect social and economic impacts.
The mathematical model in this proposed project, i.e., locating sparsest points in convex sets, is an emerging new topic that lies at the frontier of applied mathematics, engineering, information science and financial industry. Developing efficient computational methods and theory for this model is urgently needed in these fields. This is motivated and stimulated by the newly emerged compressive sensing theory that is initiating a new revolution in information science.
The applicant is convinced that the successful completion of the proposed research will have important and broad impacts on system engineering (especially in signal and image processing) and financial sectors, and in general on many end users sectors which are engaged in data processing and applications in such fields as science, control, planning, and information technologies. The results out of this project therefore will contribute to maintain and increase not only the UK's academic position in these fields, but more importantly, UK's industrial position in information technology, digital industry and medical image processing technology. The computational methods together with software developed in this project will directly help reduce the time and costs in various data processing (e.g. storage, compression, transmission, separation, and so on). This will broadly advance the design of products such as digital camera, medical scanning machine, and signal transmitter and receivers, and therefore improve the processing speed and quality of product, directly impacting on manufacturing and wealth creation as well.
Moreover, it is expected that the success of the research project will have direct or indirectly impact on any other areas that rely on this optimization model. For instance, policemen may use the face image identification and reconstruction to find the criminal, astrophysists deal with synchrotron emission images, and financial investors make their decisions under selection constraints. All these sectors require a fast, stable, powerful mathematical approach to significantly improve the efficiency, accuracy and quality of data processing.