研究了当测量矩阵从一个酉矩阵中随机子采样时的生成式压缩感知,提出了一个改进的样本复杂度的模型适应采样策略,利用非均匀随机采样分布提出了新的理论恢复保证,并优化采样分布以最小化所需测量数目,并验证了 CelebA 数据集上的恢复实验的性能。
Oct, 2023
研究如何通过几个稀疏信号线性测量(与一些固定向量的内积)的结果精确重构出稀疏的信号,并考虑了两种测量方法:高斯测量和傅里叶测量。通过几何函数分析和 Banach 空间中的随机性证明了这两种方法的最佳测量数量。
Feb, 2006
该研究论文证明了具有至多 k 非零傅里叶系数的函数在布尔超立方体上的上限,证明了学习 k-Fourier-sparse 布尔函数类所需的随机样本数量上限,同时也得出了傅里叶稀疏函数的布尔性测试的查询复杂性的上界。
Apr, 2015
稀疏均值估计算法在存在对抗性异常值的情况下的研究,提出了一种在次二次时间内运行的鲁棒稀疏均值估计算法,并在检测弱相关性方面取得了算法进展。
Mar, 2024
本文提出了一种近似过程以降低基于核的方法中 $O (N^2)$ 复杂度到 $O (N)$,通过分析基础函数的切片版本将任何径向核表示为一维核,并且导出了一维核的解析公式。通过广义 Riemann-Liouville 分数积分,我们可以将 $d$ 维核求和降低为一维设置。为了高效地解决这些一维问题,我们采用快速傅里叶求和在非等距数据上的排序算法或两者的组合。对于高斯核,我们展示了一个与维度无关的误差界限,并通过闭式傅立叶变换表示其一维对应物。同时给出了我们的快速核求和的运行时间比较和误差估计。
Jan, 2024
提供了一种高效的样本多项式时间估计器,用于高维球形高斯混合模型中,从而显着降低了时间和样本复杂度,并且还提出了针对一维混合模型的简单估计器及一种更快的算法,用于从一组分布中选择密度估计。
Feb, 2014
利用 Banach 空间中的概率新工具,将随机投影问题的研究推进到一个新的水平。其主要结果是可以线性映射任意 $N$ 个 $n$ 维实向量到一个 $O (log N polylog (n))$ 线性空间中,并在保持向量之间距离一定畸变的同时,对每个向量的映射可以在 $O (n log n)$ 时间内完成。
May, 2010
研究如何构建稀疏恢复系统,以最小化测量矩阵的数量和解码算法的运行时间,给出了一个具有优秀性能的系统,其中测量矩阵的数量与下界相匹配,且解码时间为下界的对数倍。同时还考虑了编码时间、更新时间、算法的鲁棒性和稳定性。
Dec, 2009
研究了两个基于机器学习应用中的问题:在随机线性子空间中恢复种植稀疏向量的问题以及分解随机低秩超完备三阶张量的问题。通过分析和受到二次和方法的启发,提出了新的算法,其可以在更快的时间内实现与二次和方案相似的保证
Dec, 2015
研究数据流近似算法中的函数近似问题,给出了一个条件,满足条件的函数可以进行有效的空间近似算法,解决了 Alon 等人 1996 年论文中的开放问题,并对几乎所有单变量函数进行了表征。
Jan, 2016