• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Low Rank Approximation and Decomposition of Large Matrices Using Error Correcting Codes
【24h】

Low Rank Approximation and Decomposition of Large Matrices Using Error Correcting Codes

机译：使用纠错码对大型矩阵进行低秩逼近和分解

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Low rank approximation is an important tool used in many applications of signal processing and machine learning. Recently, randomized sketching algorithms were proposed to effectively construct low rank approximations and obtain approximate singular value decompositions of large matrices. Similar ideas were used to solve least squares regression problems. In this paper, we show how matrices from error correcting codes can be used to find such low rank approximations and matrix decompositions, and extend the framework to linear least squares regression problems. The benefits of using these code matrices are the following. First, they are easy to generate and they reduce randomness significantly. Second, code matrices, with mild restrictions, satisfy the subspace embedding property, and have a better chance of preserving the geometry of an large subspace of vectors. Third, for parallel and distributed applications, code matrices have significant advantages over structured random matrices and Gaussian random matrices. Fourth, unlike Fourier or Hadamard transform matrices, which require sampling columns for a rank- approximation, the log factor is not necessary for certain types of code matrices. In particular, optimal Frobenius norm error can be achieved for a rank- approximation with samples. Fifth, fast multiplication is possible with structured code matrices, so fast approximations can be achieved for general dense input matrices. Sixth, for least squares regression problem where , the relative error approximation can be achieved with samples, with high probability, when certain code matrices are used.
机译：低秩逼近是在信号处理和机器学习的许多应用中使用的重要工具。最近，提出了一种随机素描算法，可以有效地构造低秩近似并获得大矩阵的近似奇异值分解。类似的想法被用来解决最小二乘回归问题。在本文中，我们展示了如何使用纠错码中的矩阵来查找这种低秩逼近和矩阵分解，以及如何将框架扩展到线性最小二乘回归问题。使用这些代码矩阵的好处如下。首先，它们易于生成，并且可以大大降低随机性。其次，代码矩阵具有适度的限制，可以满足子空间的嵌入特性，并且可以更好地保留矢量的大子空间的几何形状。第三，对于并行和分布式应用，代码矩阵比结构化随机矩阵和高斯随机矩阵具有明显的优势。第四，与傅里叶变换或Hadamard变换矩阵需要采样列进行秩近似不同，对于某些类型的代码矩阵，对数因子不是必需的。特别是，对于样本的秩近似，可以实现最佳Frobenius范数误差。第五，结构化代码矩阵可以实现快速乘法，因此对于一般的密集输入矩阵可以实现快速逼近。第六，对于最小二乘回归问题，其中，当使用某些代码矩阵时，可以使用样本以较高的概率实现相对误差近似。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号