Speaker
Description
Sketching techniques have gained popularity in numerical linear algebra to accelerate the solution of least squares problems. The so-called $\varepsilon$-subspace embedding property of a sketching matrix $S$ has been largely used to characterize the problem residual norm, since the procedure is no longer optimal in terms of the (classical) Frobenius or Euclidean norm. By building on available results on the SVD of the sketched matrix $SA$ derived by Gilbert, Park, and Wakin (Proc. of SPARS-2013), a novel decomposition of $A$, the $S^TS$-SVD, is proposed, which is exact with high probability, and in which the left singular vectors are orthonormal with respect to a (semi-)norm defined by the sketching matrix $S$. The new decomposition is less expensive to compute, while preserving the singular values with probabilistic confidence. In addition to present this new decomposition, in this talk we will show how the $S^TS$-SVD is the right tool to analyze the quality of several sketching techniques in the literature, for which examples are reported. For instance, it is possible to simply bound the distance from (standard) orthogonality of sketched orthogonal matrices in state-of-the-art randomized QR algorithms. If time allows, as a further application, the classical problem of the nearest orthogonal matrix will be generalized to the new $S^TS$-orthogonality, and the $S^T$S-SVD will be adopted to solve it.
