SPSD Matrix Approximation vis Column Selection: Theories, Algorithms, and Extensions

Understand

Symmetric positive semidefinite (SPSD) matrix approximation is an important problem with applications in kernel methods.

• However, existing SPSD matrix approximation methods such as the Nystr\"om method only have weak error bounds.
• In this paper we conduct in-depth studies of an SPSD matrix approximation model and establish strong relative-error bounds.
• We call it the prototype model for it has more efficient and effective extensions, and some of its extensions have high scalability.