Timezone: »
Poster
Fast and Memory Optimal LowRank Matrix Approximation
SeYoung Yun · marc lelarge · Alexandre Proutiere
In this paper, we revisit the problem of constructing a nearoptimal 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 Lowrank 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 meansquare 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
SeYoung Yun (Microsoft Research, Cambridge)
marc lelarge (INRIA  ENS)
Alexandre Proutiere (KTH)
More from the Same Authors

2019 Poster: Optimal Sampling and Clustering in the Stochastic Block Model »
SeYoung 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 »
SeYoung 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 »
SeYoung Yun · marc lelarge · Alexandre Proutiere 
2013 Poster: TwoTarget Algorithms for InfiniteArmed Bandits with Bernoulli Rewards »
Thomas Bonald · Alexandre Proutiere