384 citations · 2.3k across the 48 of their papers we have counts for
5 papers · 1 filter
More Algorithms for Provable Dictionary Learning
Sanjeev Arora, Aditya Bhaskara, Rong Ge +1
In dictionary learning, also known as sparse coding, the algorithm is given samples of the form where is an unknown random sparse vector and is an…
New Algorithms for Learning Incoherent and Overcomplete Dictionaries
Sanjeev Arora, Rong Ge, Ankur Moitra
In sparse recovery we are given a matrix (the dictionary) and a vector of the form where is sparse, and the goal is to recover . This is a central notion in signal…
Towards a better approximation for sparsest cut?
Sanjeev Arora, Rong Ge, Ali Kemal Sinop
We give a new -approximation for sparsest cut problem on graphs where small sets expand significantly more than the sparsest cut (sets of size expand by a factor $\sqr…
Testing Permanent Oracles -- Revisited
Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran +1
Suppose we are given an oracle that claims to approximate the permanent for most matrices X, where X is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate…
Computing a Nonnegative Matrix Factorization -- Provably
Sanjeev Arora, Rong Ge, Ravi Kannan +1
In the Nonnegative Matrix Factorization (NMF) problem we are given an nonnegative matrix and an integer . Our goal is to express as where and…