Check the preview of 2nd version of this platform
being developed by the open MLCommons taskforce on automation and reproducibility
as a free, open-source and technology-agnostic on-prem platform.
Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling
lib:4668a23645bc87a3 (v1.0.0)
Authors: Shusen Wang,Zhihua Zhang
ArXiv: 1303.4207
Document: PDF DOI
Abstract URL: http://arxiv.org/abs/1303.4207v7
The CUR matrix decomposition and the Nystr\"{o}m approximation are two important low-rank matrix approximation techniques. The Nystr\"{o}m method approximates a symmetric positive semidefinite matrix in terms of a small number of its columns, while CUR approximates an arbitrary data matrix by a small number of its columns and rows. Thus, CUR decomposition can be regarded as an extension of the Nystr\"{o}m approximation. In this paper we establish a more general error bound for the adaptive column/row sampling algorithm, based on which we propose more accurate CUR and Nystr\"{o}m algorithms with expected relative-error bounds. The proposed CUR and Nystr\"{o}m algorithms also have low time complexity and can avoid maintaining the whole data matrix in RAM. In addition, we give theoretical analysis for the lower error bounds of the standard Nystr\"{o}m method and the ensemble Nystr\"{o}m method. The main theoretical results established in this paper are novel, and our analysis makes no special assumption on the data matrices.
ArXiv: 1303.4207
Document: PDF DOI
Abstract URL: http://arxiv.org/abs/1303.4207v7
The CUR matrix decomposition and the Nystr\"{o}m approximation are two important low-rank matrix approximation techniques. The Nystr\"{o}m method approximates a symmetric positive semidefinite matrix in terms of a small number of its columns, while CUR approximates an arbitrary data matrix by a small number of its columns and rows. Thus, CUR decomposition can be regarded as an extension of the Nystr\"{o}m approximation. In this paper we establish a more general error bound for the adaptive column/row sampling algorithm, based on which we propose more accurate CUR and Nystr\"{o}m algorithms with expected relative-error bounds. The proposed CUR and Nystr\"{o}m algorithms also have low time complexity and can avoid maintaining the whole data matrix in RAM. In addition, we give theoretical analysis for the lower error bounds of the standard Nystr\"{o}m method and the ensemble Nystr\"{o}m method. The main theoretical results established in this paper are novel, and our analysis makes no special assumption on the data matrices.
Relevant initiatives
Related knowledge about this paper
Reproduced results (crowd-benchmarking and competitions)
Artifact and reproducibility checklists
- ACM/cTuning artifact appendix and reproducibility checklist
- NeurIPS reproducibility checklist
- SIGPLAN's checklist for empirical evaluation
- Collective Knowledge (organizing research projects based on FAIR principles)