Research map / Learning theory and algorithms / Matrix and tensor methods
Efficient Anomaly Detection via Matrix Sketching
Vatsal Sharan, Parikshit Gopalan, Udi Wieder
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sketching instead of full SVD to compute rank-k projection distances | Anomaly score computation · p53 mutants, Dorothea, and RCV1 | runtime: Speedups between 2× and 6× | Improved |
| Use Random Column Projection rather than Random Row Projection | Anomaly score approximation · Most settings | F1 | Improved |
| Choose sketch dimension ℓ as a small multiple of k | Sketch-based anomaly detection · Most experimental settings | F1: >0.75 F1 with C ≈ 10 | Improved |
| Use sketch-based anomaly scores with more than 10× space savings | p53 mutants · p53 mutants | F1: F1 score >0.8 with >10× space savings | Improved |
| Use Random Column Projection rather than Random Row Projection | Anomaly score approximation · Dorothea | F1 | Improved |
| Apply sketching to data with less pronounced low-rank structure | Sketch-based anomaly detection · RCV1 | F1 | Hurt |
Closest papers by meaning
- Precise expressions for random projections: Low-rank approximation and randomized Newton (NeurIPS 2020 · similarity 0.86)
- Fixed-Parameter and Approximation Algorithms for PCA with Outliers (ICML 2021 · similarity 0.86)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.85)
- Matrix Product Sketching via Coordinated Sampling (ICLR 2025 · similarity 0.84)
- Multi-Subspace Matrix Recovery from Permuted Data (AAAI 2025 · similarity 0.84)
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
