图 书 馆
随机化还是压缩？通过级联压缩采样绘制 LinearCost 矩阵草图Randomization or Condensation? LinearCost Matrix Sketching Via Cascaded Compression Sampling |
|
| 课程网址: | http://videolectures.net/kdd2017_zhang_linear_cost_matrix/ |
| 主讲教师: | Kai Zhang |
| 开课单位: | 天普大学 |
| 开课时间: | 2017-10-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Matrix sketching is aimed at finding compact representations of a matrix while simultaneously preserving most of its properties, which is a fundamental building block in modern scientific computing. Randomized algorithms represent state-of-the-art and have attracted huge interest from the fields of machine learning, data mining, and theoretic computer science. However, it still requires the use of the entire input matrix in producing desired factorizations, which can be a major computational and memory bottleneck in truly large problems. In this paper, we uncover an interesting theoretic connection between matrix low-rank decomposition and lossy signal compression, based on which a cascaded compression sampling framework is devised to approximate an m-by-n matrix in only O(m+n) time and space. Indeed, the proposed method accesses only a small number of matrix rows and columns, which significantly improves the memory footprint. Meanwhile, by sequentially teaming two rounds of approximation procedures and upgrading the sampling strategy from a uniform probability to more sophisticated, encoding-orientated sampling, significant algorithmic boosting is achieved to uncover more granular structures in the data. Empirical results on a wide spectrum of real-world, large-scale matrices show that by taking only linear time and space, the accuracy of our method rivals those state-of-the-art randomized algorithms consuming a quadratic, O(mn), amount of resources. |
| 关 键 词: | 级联压缩采样; 矩阵草图; 数据科学 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2023-12-27：wujk |
| 最后编审: | 2023-12-27：wujk |
| 阅读次数: | 19 |