Fetching the paper…
Reading the bibliography…
We study exact recovery conditions for convex relaxations of point cloud clustering problems, focusing on two of the most common optimization problems for unsupervised clustering: $k$-means and $k$-median clustering.
Least squares quantization in pcm
S. Lloyd · 1982
Earlier work this paper cites.
Theory of Linear and Integer Programming
A. Schrijver · 1986
Earlier work this paper cites.
Learning mixtures of gaussians
S. Dasgupta · 1999
Earlier work this paper cites.
Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation
K. Jain and V. V. Vazirani · 2001
Earlier work this paper cites.
Approximation Algorithms
V. V. Vazirani · 2001
Earlier work this paper cites.
A new greedy approach for facility location problems
K. Jain, M. Mahdian, and A. Saberi · 2002
Earlier work this paper cites.
A local search approximation algorithm for k-means clustering
T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu · 2002
Earlier work this paper cites.
Local search heuristics for k-median and facility location problems
V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit · 2004
Earlier work this paper cites.
On clusterings: good, bad and spectral
R. Kannan, S. Vempala, and A. Vetta · 2004
Earlier work this paper cites.
On spectral learning of mixtures of distributions
D. Achlioptas and F. McSherry · 2005
Earlier work this paper cites.
Learning mixtures of arbitrary gaussians
S. Arora and R. Kannan · 2005
Earlier work this paper cites.
Using linear programming to decode binary linear codes
J. Feldman, M. Wainwright, and D. Karger · 2005
Earlier work this paper cites.
A new theoretical framework for k k -means-type clustering
J. Peng and Y. Xia · 2005
Earlier work this paper cites.
Stable signal recovery from incomplete and inaccurate measurements
E. Candès, J. Romberg, and T. Tao · 2006
Earlier work this paper cites.
Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information
E. J. Candès, J. Romberg, and T. Tao · 2006
Earlier work this paper cites.
Compressed sensing
D. Donoho · 2006
Earlier work this paper cites.
The effectiveness of lloyd-type methods for the k-means problem
R. Ostrovsky, Y. Rabani, L. Schulman, and C. Swamy · 2006
Earlier work this paper cites.
k-means++: the advantages of careful seeding
D. Arthur and S. Vassilvitskii · 2007
Earlier work this paper cites.
LP decoding corrects a constant fraction of errors
J. Feldman, T. Malkin, R. Servedio, C. Stein, and M. Wainwright · 2007
Earlier work this paper cites.
Approximating k-means-type clustering via semidefinite programming
J. Peng and Y. Wei · 2007
Cited alongside, same era.
A discriminative framework for clustering via similarity functions
M. Balcan, A. Blum, and S. Vempala · 2008
Cited alongside, same era.
Isotropic PCA and affine-invariant clustering
S. C. Brubaker and S. Vempala · 2008
Cited alongside, same era.
Probabilistic analysis of linear programming decoding
C. Daskalakis, A. Dimakis, R. M. Karp, and M. Wainwright · 2008
Cited alongside, same era.
Beyond loose lp-relaxations: Optimizing mrfs by repairing cycles
N. Komodakis and N. Paragios · 2008
Cited alongside, same era.
Tightening LP relaxations for MAP using message passing
D. Sontag, T. Meltzer, A. Globerson, T. Jaakkola, and Y. Weiss · 2008
Cited alongside, same era.
A simpler approach to matrix completion
B. Recht · 2011
Later among the works it cites.
Introduction to the non-asymptotic analysis of random matrices
R. Vershynin · 2011
Later among the works it cites.
Guaranteed clustering and biclustering via semidefinite programming
B. Ames · 2012
Later among the works it cites.
Clustering under perturbation resilience
M.-F. Balcan and Y. Liang · 2012
Later among the works it cites.
Clustering sparse graphs
Y. Chen, S. Sanghavi, and H. Xu · 2012
Later among the works it cites.
Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery
E. Elhamifar, G. Sapiro, and R. Vidal · 2012
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
NP-hardness of euclidean sum-of-squares clustering
D. Aloise, A. Deshpande, P. Hansen, and P. Popat · 2009
Cited alongside, same era.
Message passing algorithms and improved LP decoding
S. Arora, C. Daskalakis, and D. Steurer · 2009
Cited alongside, same era.
Approximate clustering without the approximation
M. Balcan, A. Blum, and A. Gupta · 2009
Cited alongside, same era.
Learning mixtures of gaussians using the k-means algorithm
K. Chaudhuri, S. Dasgupta, and A. Vattani · 2009
Cited alongside, same era.
Are stable instances easy?
Y. Bilu and N. Linial · 2010
Cited alongside, same era.
The power of convex relaxation: Near-optimal matrix completion
E. J. Candès and T. Tao · 2010
Cited alongside, same era.
k-means++ under approximation stability
M. Agarwal, R. Jaiswal, and A. Pal · 2013
Later among the works it cites.
Robust convex relaxation for the planted clique and densest k-subgraph problems
B. Ames · 2013
Later among the works it cites.
Convex relaxation for finding planted influential nodes in a social network
L. Elkin, T. Pong, and S. Vavasis · 2013
Later among the works it cites.
Approximating k-median via pseudo-approximation
S. Li and O. Svensson · 2013
Later among the works it cites.
Recovery guarantees for exemplar-based clustering
A. Nellore and R. Ward · 2013
Later among the works it cites.
Exact recovery in the stochastic block model
E. Abbe, A. S. Bandeira, and G. Hall · 2014
Closest in time.
Multireference alignment using semidefinite programming
A. S. Bandeira, M. Charikar, A. Singer, and A. Zhu · 2014
Closest in time.
Open problem: Tightness of maximum likelihood semidefinite relaxations
A. S. Bandeira, Y. Khoo, and A. Singer · 2014
Closest in time.
Coherent matrix completion
Y. Chen, S. Bhojanapalli, S. Sanghavi, and R. Ward · 2014
Closest in time.
Y. Chen and J. Xu · 2014
Closest in time.
CVX: Matlab software for disciplined convex programming, version 2.1
M. Grant and S. Boyd · 2014
Closest in time.
Bilu-linial stable instances of max cut and minimum multiway cut
K. Makarychev, Y. Makarychev, and A. Vijayaraghavan · 2014
Closest in time.
Consistency thresholds for binary symmetric block models
E. Mossel, J. Neeman, and A. Sly · 2014
Closest in time.