几乎线性化稀疏化的高维 l_p 子空间逼近
内容提要
本文研究了在多维欧氏空间中寻找 k 维子空间以最小化 n 个点到该子空间的 p 次方欧氏距离和的问题。探讨了特定损失函数下的最优解，并提出了增强对离群值鲁棒性的鲁棒子空间算法。此外，介绍了多元回归、低失真度嵌入和稀疏主成分分析等相关方法及其实际应用效果。
延伸解读
鲁棒子空间逼近的动机
传统子空间逼近通常依赖奇异值分解（SVD），但SVD对离群值敏感。本文探讨在Huber和Tukey等损失函数下的最优解，这些鲁棒子空间可替代SVD，对典型M-Estimators提供更强的离群值鲁棒性。文章还给出了相关算法和难度结果，为处理含噪声或异常点的数据提供了理论工具。
核心集与多元回归的近似界限
通过构建核心集，本文实现了对多个响应的多元回归目标的近似，并得到了关于样本数量和子空间逼近的几乎最优界限。这意味着在大规模数据下，可以用较小的核心集代表原始数据，从而高效地近似求解回归问题，同时保证理论上的近似质量。
稀疏主成分分析的稀疏性概念
针对高维稀疏主成分分析，本文提出了行稀疏和列稀疏的lq子空间稀疏概念，并为0≤q≤1证明了极小化子空间估计误差的非渐近下限和上限。该限制完美适用于行稀疏子空间，近乎适用于列稀疏子空间。证明中使用了一种新颖的变分sinΘ定理，可能对其他正则化谱估计问题有启发。
稀疏嵌入矩阵与快速近似
本文提出一种新的稀疏嵌入矩阵，利用它可实现超约束最小二乘回归、低秩逼近、所有梁角得分的近似以及l_p回归问题的(1+ε)-近似，时间复杂度主导项为O(nnz(A))或O(nnz(A)log n)。这为大规模稀疏数据下的线性代数问题提供了高效算法。
Q&A
如何在多维欧氏空间中寻找 k 维子空间以最小化点到子空间的距离？
可以通过研究特定损失函数下的最优解来实现，例如使用 Huber 和 Tukey 损失函数。
鲁棒子空间算法的优势是什么？
鲁棒子空间算法比奇异值分解（SVD）更有效，尤其在处理离群值时具有更强的鲁棒性。
低失真度嵌入方法的应用是什么？
低失真度嵌入方法广泛应用于线性代数问题，支持 l_2 误差损失最小回归和 l_p 子空间嵌入。
高维稀疏主成分分析的关键概念是什么？
高维稀疏主成分分析提出了行稀疏和列稀疏的 lq 子空间稀疏概念，并研究了子空间估计误差的上下限。
如何解决 Lp 回归问题？
可以使用有效的两阶段抽样算法，包括构建核心集合和采样方法来解决 Lp 回归问题。
社会公正聚类中的近似算法是如何工作的？
该算法通过在度量空间中找到 k-中位数或 k-均值来满足多个组的需求，并应用强化的 LP 松弛。
