Sparse linear models: Their existence and stability

生活的许多领域都收集了大量的数据，包括医疗、金融、零售、工业和社交媒体领域。必须对这些数据进行分析，以便能够提取其属性并了解基本系统。有必要区分可能很大的数据量和数据中包含的信息，这些信息可以使数据以可接受的精度用一个简单的模型表示。这个简单的模型捕获了系统的基本属性，因此它可以用于确定系统对新的(看不见的)数据的响应。简单模型的一个例子是低次多项式，但是这个建议考虑了稀疏模型，这是简单模型的另一个例子。系统的稀疏模型是这样一种模型，在该模型中，确定了决定输出的主要输入变量(预测器)，而不是所有的输入变量。基因组学提供了稀疏模型的一个例子，因为人体中大约有3万个基因，但并不是所有的基因都与癌症直接相关。因此，确定与癌症最直接相关的基因是可取的，以便将治疗重点放在主要的促成因素上，而不是那些在癌症病因中起次要作用的因素。线性代数方程Ax=b的解x的稀疏性是通过1范数(套索)的正则化来施加的。这不同于2范数中的正则化(Tikhonov正则化)，后者对x施加稳定性。套索和Tikhonov正则化不被理解，因为没有1范数矩阵分解，但Ax=b的正则化解的基本性质与施加正则化的范数无关。例如，在两个范数中的正则化解必须是稳定的，并且它与精确解之间的误差必须很小。当使用套索正则化时，该方案考虑了正则解的这些性质。一般来说，在稀疏模型上的计算比在精确稠密模型上的计算更简单、更快，这是有利的，并且在该方案中考虑了必须解决的重要理论问题。稀疏模型是精确稠密模型的近似，因此存在与稀疏模型相关的误差。一个好的稀疏模型是这样一个模型，其中的误差很小，而这个稀疏模型之所以被接受，是因为稀疏模型允许的更大的物理洞察力平衡了这个小误差。此外，稀疏模型必须在计算上可靠，因此从它得到的结果在数值上是稳定的，因此一个好的稀疏模型必须具有小的误差并且是稳定的。然而，不能假设所有的输入都产生一种近似的、稀疏的、稳定的、误差很小的投入产出关系。因此，有必要确定满足和不满足这些性质的输入类别。因此，在确信稀疏模型的正确性之前，有许多问题需要考虑。这项提案解决了这些问题，它将包括理论结果和计算实验。拟议研究的好处扩展到许多领域，在这些领域中，稀疏模型被用来模拟投入产出关系。这些应用包括医疗、金融、零售、工业和社交媒体领域(如上所述)。除了稀疏模型的计算优势(如上所述)外，稀疏模型的可取之处在于其简单性，因此更容易获得对系统输入-输出关系的物理理解。

Large quantities of data are gathered in many domains of life, including the medical, financial, retail, industrial and social media domains. This data must be analysed such that its properties can be extracted and the underlying system understood. It is necessary to distinguish between the quantity of data, which may be large, and the information contained in the data, which may allow it to be represented, with acceptable accuracy, by a simple model. This simple model captures fundamental properties of the system, such that it can be used for the determination of the response of the system on new (unseen) data. An example of a simple model is a low degree polynomial, but this proposal considers a sparse model, which is another example of a simple model. A sparse model of a system is a model in which the dominant input variables (predictors) that determine the output, rather than all the input variables, are identified. Genomics provides an example of a sparse model because there are about 30,000 genes in the human body, but not all genes are associated directly with cancer. It is therefore desirable to identify the genes that are most directly associated with cancer, such that treatment is focused on the dominant contributory factors, rather than factors whose role in the cause of cancer is minor. Sparsity of the solution x of the linear algebraic equation Ax=b is imposed by regularisation in the 1-norm (the lasso). This is different from regularisation in the 2-norm (Tikhonov regularisation), which imposes stability on x. The lasso is not understood as well as Tikhonov regularisation because of the absence of a 1-norm matrix decomposition, but fundamental properties of a regularised solution of Ax=b are independent of the norm in which the regularisation is imposed. For example, a regularised solution in both norms must be stable and the error between it and the exact solution must be small. This proposal considers these properties of a regularised solution when regularisation by the lasso is used.Computations on sparse models are, in general, simpler and faster than computations on exact dense models, which is advantageous, and important theoretical issues that must be addressed are considered in this proposal. A sparse model is an approximation of an exact dense model and there is therefore an error associated with a sparse model. A good sparse model is a model in which this error is small, and this sparse model is accepted because this small error is balanced by the greater physical insight allowed by a sparse model. Furthermore, a sparse model must be computationally reliable such that results derived from it are numerically stable, and thus a good sparse model must have a small error and be stable. It cannot, however, be assumed that all inputs yield an approximate input-output relationship that is sparse, stable and has a small error. It is therefore necessary to establish the class of inputs for which these properties are, and are not, satisfied. It follows that there are many issues to be considered before a sparse model can be used with confidence of its correctness. This proposal addresses these issues and it will include theoretical results and computational experiments. The benefits of the proposed research extend to the many areas in which a sparse model is used to model an input-output relationship. These applications include the medical, financial, retail, industrial and social media domains (as stated above). Apart from the computational advantages of a sparse model (stated above), the desirability of a sparse model follows from its simplicity, and it is therefore easier to obtain a physical understanding of the input-output relationship of the system.