Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms.

Area of Science:

• Numerical Analysis
• Computer Science
• Data Science

Background:

• Residual error estimation is crucial for assessing the utility of low-rank approximations in matrices.
• Approximating matrix and vector norms is fundamental in various data analysis tasks, including heavy hitter identification.
• Existing methods for residual error estimation can be computationally expensive.

Purpose of the Study:

• To develop efficient linear sketching techniques for estimating residual errors in matrix and vector norms.
• To improve the bounds on sketch size for approximating the Frobenius norm residual of matrices.
• To establish new bounds for approximating vector ${\ell }_p$ -norms and for ${\ell }_p$ sparse recovery.

Main Methods:

• Utilized bilinear sketches of the form $SAT$ for matrix residual error estimation.
• Developed algorithms employing sparse sketching matrices for fast updates.
• Applied linear sketches to approximate vector ${\ell }_p$ -norms and for ${\ell }_p$ sparse recovery.

Main Results:

• Established a tight bound of $\Theta \left(k^2/{\epsilon }^4\right)$ on the size of bilinear sketches for matrix Frobenius norm residuals, improving upon previous bounds.
• Achieved an upper bound of $O\left(k^{2/p}{n}^{1-2/p}\right)$ poly $\left(\left(\text{log}n\right)\right)$ for vector ${\ell }_p$ -norm approximation and ${\ell }_p$ sparse recovery for $p>2$.
• Provided matching lower bounds for the vector ${\ell }_p$ sparse recovery problem.

Conclusions:

• The proposed sketching methods offer significant improvements in efficiency and accuracy for residual error estimation.
• Sparse sketching matrices enable faster computations with empirical advantages.
• The results provide foundational bounds for advanced data stream analysis and sparse recovery problems.