Timezone: »
Poster
Fast and Memory Optimal Low-Rank Matrix Approximation
Se-Young Yun · marc lelarge · Alexandre Proutiere
In this paper, we revisit the problem of constructing a near-optimal rank $k$ approximation of a matrix $M\in [0,1]^{m\times n}$ under the streaming data model where the columns of $M$ are revealed sequentially. We present SLA (Streaming Low-rank Approximation), an algorithm that is asymptotically accurate, when $k s_{k+1} (M) = o(\sqrt{mn})$ where $s_{k+1}(M)$ is the $(k+1)$-th largest singular value of $M$. This means that its average mean-square error converges to 0 as $m$ and $n$ grow large (i.e., $\|\hat{M}^{(k)}-M^{(k)} \|_F^2 = o(mn)$ with high probability, where $\hat{M}^{(k)}$ and $M^{(k)}$ denote the output of SLA and the optimal rank $k$ approximation of $M$, respectively). Our algorithm makes one pass on the data if the columns of $M$ are revealed in a random order, and two passes if the columns of $M$ arrive in an arbitrary order. To reduce its memory footprint and complexity, SLA uses random sparsification, and samples each entry of $M$ with a small probability $\delta$. In turn, SLA is memory optimal as its required memory space scales as $k(m+n)$, the dimension of its output. Furthermore, SLA is computationally efficient as it runs in $O(\delta kmn)$ time (a constant number of operations is made for each observed entry of $M$), which can be as small as $O(k\log(m)^4 n)$ for an appropriate choice of $\delta$ and if $n\ge m$.
Author Information
Se-Young Yun (Microsoft Research, Cambridge)
marc lelarge (INRIA - ENS)
Alexandre Proutiere (KTH)
More from the Same Authors
-
2021 Poster: Fast Pure Exploration via Frank-Wolfe »
Po-An Wang · Ruo-Chun Tzeng · Alexandre Proutiere -
2021 Poster: Navigating to the Best Policy in Markov Decision Processes »
Aymen Al Marjani · AurĂ©lien Garivier · Alexandre Proutiere -
2020 Poster: Regret in Online Recommendation Systems »
Kaito Ariu · Narae Ryu · Se-Young Yun · Alexandre Proutiere -
2020 Poster: Optimal Best-arm Identification in Linear Bandits »
Yassir Jedra · Alexandre Proutiere -
2019 Poster: Optimal Sampling and Clustering in the Stochastic Block Model »
Se-Young Yun · Alexandre Proutiere -
2018 Poster: Exploration in Structured Reinforcement Learning »
Jungseul Ok · Alexandre Proutiere · Damianos Tranos -
2018 Oral: Exploration in Structured Reinforcement Learning »
Jungseul Ok · Alexandre Proutiere · Damianos Tranos -
2017 Poster: Minimal Exploration in Structured Stochastic Bandits »
Richard Combes · Stefan Magureanu · Alexandre Proutiere -
2017 Spotlight: Minimal Exploration in Structured Stochastic Bandits »
Richard Combes · Stefan Magureanu · Alexandre Proutiere -
2016 Poster: Optimal Cluster Recovery in the Labeled Stochastic Block Model »
Se-Young Yun · Alexandre Proutiere -
2015 Poster: Combinatorial Bandits Revisited »
Richard Combes · M. Sadegh Talebi · Alexandre Proutiere · marc lelarge -
2014 Poster: Streaming, Memory Limited Algorithms for Community Detection »
Se-Young Yun · marc lelarge · Alexandre Proutiere -
2013 Poster: Two-Target Algorithms for Infinite-Armed Bandits with Bernoulli Rewards »
Thomas Bonald · Alexandre Proutiere