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

在过去的几年里，在结构良好的凸集中寻找稀疏解/点的数学模型在各个学科中都产生了重大影响。在信号恢复和去噪、图像重建和修复、人脸识别、统计估计、模式识别、模型选择、机器学习、金融工程等领域中，寻求稀疏性已经成为一项共同的要求和任务。然而，这仍然是一个正在出现的新领域，需要紧急和广泛的科学研究投入。拟议的项目旨在通过提供复杂的计算方法和相关理论，在这一领域做出重大贡献。这项研究的成果将直接有益于学术界和工程界。到目前为止，NP-hard稀疏搜索模型的研究主要采用凸近似方法，即，l1方法虽然它成功地解决了广泛的稀疏搜索问题，但它也可能在许多情况下失败。重新加权的方法已经被数值证明能够在许多情况下优于l1方法。然而，到目前为止，对重加权算法的理论分析是非常有限的，与此方法相关的许多基本问题仍然是开放的。因此，当务之急是制定一个严格的理论和有效的设计，目前，躺在应用数学和工程的研究前沿的重加权算法。本项目旨在对这一理论和设计进行全面、系统的研究，全面或部分地解决这一领域的一些重要问题，并将所发展的理论和算法及时应用于数据处理，特别是信号和图像处理以及金融问题。具有多学科性质，拟议的研究涉及应用数学（计算优化和数值分析），工程（稀疏数据表示和处理）和计算机科学（算法设计和复杂性）之间的大量思想交流。我们的目标是实现四个密切相关的目标。成功地完成其中一个目标将为下一个目标的实现带来有益的想法。首先，我们的目标是加强现有的理论和方法，通过开发新的和宽松的条件，保证成功的加权和非加权的方法定位稀疏点的凸集。其次，我们的目标是为稀疏搜索问题的一般模型开发一个通用算法框架和收敛理论，从而在计算优化方面开辟一个新的前沿，并刺激工业部门中更多潜在的复杂应用。此外，还将编制用于研究目的（以后可能用于商业目的）的计算机程序。我们的第三个目标是通过深入探索和确定性地证明重新加权和非加权算法之间的相互作用，使学术界受益。到目前为止，这一重要的研究还没有在这一领域进行。此外，我们的目标是重新加权算法的效率和凹极小化问题之间的深层关系，导致全局优化，快速数据处理和计算复杂性之间的新的研究前沿。

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.