Robust Partially-Compressed Least-Squares
Robust Partially-Compressed Least-Squares
复制标题
鲁棒部分压缩最小二乘法
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Marek Petrik
中科院分区：
文献类型：
--
作者：
Stephen Becker;B. Kawas;Marek Petrik
随机矩阵压缩技术，如Johnson-Lindenstrauss变换，已经成为有效解决大规模问题的有效和实用的方法。然而，随着对计算效率的关注，放弃解决方案的质量和准确性成为权衡。在本文中，我们研究压缩的最小二乘问题，并提出新的模型和算法，解决压缩引入的误差和噪声的问题。在保持计算效率的同时，我们的模型提供了比经典压缩变体更准确的鲁棒解决方案。我们介绍了强大的优化工具，连同一种形式的部分压缩，以提高压缩最小二乘求解器的误差时间权衡。我们开发了一个有效的解决方案算法，我们的鲁棒部分压缩（RPC）模型的基础上减少到一维搜索。
Randomized matrix compression techniques, such as the Johnson-Lindenstrauss transform, have emerged as an effective and practical way for solving large-scale problems efficiently. With a focus on computational efficiency, however, forsaking solutions quality and accuracy becomes the trade-off. In this paper, we investigate compressed least-squares problems and propose new models and algorithms that address the issue of error and noise introduced by compression. While maintaining computational efficiency, our models provide robust solutions that are more accurate than those of classical compressed variants. We introduce tools from robust optimization together with a form of partial compression to improve the error-time trade-offs of compressed least-squares solvers. We develop an efficient solution algorithm for our Robust Partially-Compressed (RPC) model based on a reduction to a one-dimensional search.