Proximal methods for sparse optimal scoring and discriminant analysis
Proximal methods for sparse optimal scoring and discriminant analysis
复制标题
DOI：
10.1007/s11634-022-00530-6
复制
发表时间：
2017-05
影响因子：
1.6
通讯作者：
S. Atkins;Gudmundur Einarsson;L. Clemmensen;Brendan P. W. Ames
中科院分区：
文献类型：
--
作者：
S. Atkins;Gudmundur Einarsson;L. Clemmensen;Brendan P. W. Ames
线性判别分析(LDA)是一种经典的降维方法，通过寻找判别向量将数据投影到低维空间，从而实现类的最优可分性。最近的几篇论文概述了基于利用判别向量的稀疏性的策略，用于在特征数量超过数据中的观测数量的高维环境中执行LDA。然而，许多已提出的方法缺乏可伸缩的方法来解决底层的优化问题。我们考虑了一种基于块坐标下降的LDA稀疏最优评分公式的优化方案。该算法的每一次迭代都需要更新一个评分向量，其中包含一个解析公式，并更新相应的判别向量，这需要解一个凸子问题；我们将提出该算法的几个变种，其中使用近似梯度法或乘子的交替方向法来求解该子问题。我们证明了在使用受限正则化项的情况下，这些方法的每次迭代代价与数据的维度成线性关系，而在最坏的情况下，每次迭代的代价与数据的维度成三次关系。进一步，我们证明了当这个块坐标下降框架产生收敛的迭代子序列时，这些子序列收敛到稀疏最优评分问题的固定点。我们用实验结果证明了我们的新方法对高斯型数据和来自基准数据库的数据集的分类的有效性，包括时间序列和多光谱X射线数据，并给出了我们的优化方案的数据标签和R实现。
Linear discriminant analysis (LDA) is a classical method for dimensionality reduction, where discriminant vectors are sought to project data to a lower dimensional space for optimal separability of classes. Several recent papers have outlined strategies, based on exploiting sparsity of the discriminant vectors, for performing LDA in the high-dimensional setting where the number of features exceeds the number of observations in the data. However, many of these proposed methods lack scalable methods for solution of the underlying optimization problems. We consider an optimization scheme for solving the sparse optimal scoring formulation of LDA based on block coordinate descent. Each iteration of this algorithm requires an update of a scoring vector, which admits an analytic formula, and an update of the corresponding discriminant vector, which requires solution of a convex subproblem; we will propose several variants of this algorithm where the proximal gradient method or the alternating direction method of multipliers is used to solve this subproblem. We show that the per-iteration cost of these methods scales linearly in the dimension of the data provided restricted regularization terms are employed, and cubically in the dimension of the data in the worst case. Furthermore, we establish that when this block coordinate descent framework generates convergent subsequences of iterates, then these subsequences converge to the stationary points of the sparse optimal scoring problem. We demonstrate the effectiveness of our new methods with empirical results for classification of Gaussian data and data sets drawn from benchmarking repositories, including time-series and multispectral X-ray data, and provideMatlabandRimplementations of our optimization schemes.