Improved Practical Matrix Sketching with Guarantees

Understand

Matrices have become essential data representations for many large-scale problems in data analytics, and hence matrix sketching is a critical task.

• Although much research has focused on improving the error/size tradeoff under various sketching paradigms, the many forms of error bounds make these approaches hard to compare in theory and in practice.
• This paper attempts to categorize and compare most known methods under row-wise streaming updates with provable guarantees, and then to tweak some of these methods to gain practical improvements while retaining guarantees.
• For instance, we observe that a simple heuristic iSVD, with no guarantees, tends to outperform all known approaches in terms of size/error trade-off.