稀疏线性回归（SLR）是一个在统计学中研究得很多的问题，在该问题中，给定一个设计矩阵 X 和一个响应向量 y，目标是寻找一个最小化均方预测误差的 k - 稀疏向量 hat (theta)，该问题在设计矩阵良好条件下可以通过 L1 松弛方法解决，本文提供了关于所有有效算法的平均情况困难性证据，并基于格问题的最差情况困难性给出了 SLR 的平均情况困难性证据，同时还讨论了可辨别与不可辨别的情形。

Feb, 2024

该研究提出了两种随机算法来更快地找到无精确解的线性方程组的最小二乘近似解，这两种算法均使用随机哈达玛变换对数据进行预处理，并利用随机抽样约束或进行稀疏随机投影，并在较短时间内提供相对误差逼近的解决方案。

Oct, 2007

研究稀疏优化问题中的算法和局限性，探索稀疏线性回归和鲁棒线性回归问题，在此基础上展示了鲁棒回归问题的二准则、NP - 近似困难性，给出了一个使用近似最近邻数据结构的鲁棒回归算法，并且介绍了一个从鲁棒线性回归到稀疏线性回归的通用带宽率约化算法。

Jun, 2022

本文提出了一种新的稀疏嵌入矩阵，通过使用这种矩阵，可以实现超约束最小二乘回归、低秩逼近、所有梁角得分的近似和 $l_p$- 回归问题的 $(1+\varepsilon)$- 近似，其时间复杂度的主导项是 $O (\nnz (A))$ 或 $O (\nnz (A)\log n)$。

Jul, 2012

本文研究了距离矩阵的低秩近似，证明了在任何底层距离度量下，均可以在亚线性时间内实现加性误差的低秩近似，并发展了一种基于投影 - 成本保持抽样的递归算法。同时，在一般情况下，相对误差逼近是不可能的，即使允许二标准解决方案。此外，如果 P = Q 并且 d 是欧几里得平方距离，则可以在亚线性时间内找到相对误差的二标准解决方案。

Sep, 2018

研究了度量空间中近似最近邻的问题，其中查询点被限制在低重复维度的子空间上，而数据则是高维的。我们展示了尽管数据是高维的，这个问题仍能得到有效的解决。

Jul, 2010

研究了高维线性回归在对抗性污染下的稳健模型问题，并针对从高斯分布生成的未被修正的样本的基本情况给出了几乎最紧的上界和计算下界。

May, 2018

我们研究了稀疏线性回归的计算统计缺口，证明了这个问题需要至少大约 k^2 个样本才能有效解决，并且还应用于稀疏 PCA 问题的降低及低阶下界。

Feb, 2024

本文提出了一个解决低秩和 / 或稀疏矩阵最小化问题的一般框架，使用迭代重新加权最小二乘（IRLS）方法来解决混合低秩和稀疏最小化问题，例如用于解决 Schatten-p 规范和 ell_2,q-norm 规范的低秩表示问题，理论证明了所获得的解为静止点，并在合成和实际数据集上进行了广泛的实验以证明其有效性。

Jan, 2014

在本文中，我们重新考虑了局部差分隐私（LDP）模型下稀疏线性回归的问题。我们提出了一种创新的非交互式局部差分隐私（NLDP）算法，该算法在数据服从亚高斯分布的情况下，为估计误差提供了上界，并且在服务器有额外公开但未标记数据的情况下，误差上界可以进一步提高。我们还研究了序贯交互式 LDP 模型，并发现了非私有情况、中心差分隐私模型和局部差分隐私模型在稀疏线性回归问题上的基本差异。

Oct, 2023