English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We prove, using the subspace embedding guarantee in a black box way, that onecan achieve the spectral norm guarantee for approximate matrix multiplicationwith a dimensionality-reducing map having $m = O(\tilde{r}/\varepsilon^2)$rows. Here $\tilde{r}$ is the maximum stable rank, i.e. squared ratio ofFrobenius and operator norms, of the two matrices being multiplied. This is aquantitative improvement over previous work of [MZ11, KVZ14], and is alsooptimal for any oblivious dimensionality-reducing map. Furthermore, due to theblack box reliance on the subspace embedding property in our proofs, ourtheorem can be applied to a much more general class of sketching matrices thanwhat was known before, in addition to achieving better bounds. For example, onecan apply our theorem to efficient subspace embeddings such as the SubsampledRandomized Hadamard Transform or sparse subspace embeddings, or even withsubspace embedding constructions that may be developed in the future.  Our main theorem, via connections with spectral error matrix multiplicationshown in prior work, implies quantitative improvements for approximate leastsquares regression and low rank approximation. Our main result has also alreadybeen applied to improve dimensionality reduction guarantees for $k$-meansclustering [CEMMP14], and implies new results for nonparametric regression[YPW15].  We also separately point out that the proof of the "BSS" deterministicrow-sampling result of [BSS12] can be modified to show that for any matrices$A, B$ of stable rank at most $\tilde{r}$, one can achieve the spectral normguarantee for approximate matrix multiplication of $A^T B$ by deterministicallysampling $O(\tilde{r}/\varepsilon^2)$ rows that can be found in polynomialtime. The original result of [BSS12] was for rank instead of stable rank. Ourobservation leads to a stronger version of a main theorem of [KMST10].

Optimal approximate matrix product in terms of stable rank