SᵀS‑SVD via sketching and the nearest SᵀS‑orthogonal matrix

Sketching techniques have gained popularity in numerical linear algebra to accelerate the solution of least squares problems. The so-called ε-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⊤S-SVD, is proposed, which holds 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 than the standard SVD, while preserving the singular values with probabilistic confidence. The S⊤S-SVD appears to be the right tool to analyze the quality of several sketching-based techniques in the literature, for which examples are reported. For instance, it is possible to simply bound the distance from (standard) orthogonality of sketching-based orthogonal matrices in state-of-the-art randomized algorithms for QR factorizations. As an application, the classical problem of the nearest orthogonal matrix is generalized to the new S⊤S-orthogonality, and the S⊤S-SVD is used to solve it. Probabilistic bounds on the quality of the solution are also derived.