Greedy Column Subset Selection: New Bounds and Distributed Algorithms
Skip to main content
Explore our many areas of focus
Explore all research areas
Applied AI & sciences
Earth AI
Health AI
Science AI
Sustainability & crisis resilience
Foundational ML & algorithms
Algorithms & theory
Information retrieval
Machine intelligence
Machine perception
Natural language processing
People, systems & quantum AI
Human-computer interaction and visualization
Networking
Quantum AI
Responsible AI
Anti abuse
Software engineering
Software systems
Learn More
Publications
Projects
Building a collaborative ecosystem
Datasets
Access high-quality datasets to accelerate your research.
Tools & services
Explore our latest AI models and products.
Open source
Discover open-source code and collaborate with the community.
Shaping the future together
See all programs
Faculty programs
Participating in the academic research community through meaningful engagement with university faculty.
Student programs
Supporting the next generation of researchers through a wide range of programming.
Locations
Find your place in our global offices and research labs.
Translating discovery into real-world impact
People
Our researchers drive advancements in computer science through both fundamental and applied research.
Teams
Collaborative groups tackling the world's most challenging AI problems.
Research
Explore our many areas of focus
Explore all research areas
Applied AI & sciences
Earth AI
Health AI
Science AI
Sustainability & crisis resilience
Foundational ML & algorithms
Algorithms & theory
Information retrieval
Machine intelligence
Machine perception
Natural language processing
People, systems & quantum AI
Human-computer interaction and visualization
Networking
Quantum AI
Responsible AI
Anti abuse
Software engineering
Software systems
Learn More
Publications
Projects
Resources
Building a collaborative ecosystem
Datasets
Access high-quality datasets to accelerate your research.
Tools & services
Explore our latest AI models and products.
Open source
Discover open-source code and collaborate with the community.
Conferences & events
Careers
Shaping the future together
See all programs
Faculty programs
Participating in the academic research community through meaningful engagement with university faculty.
Student programs
Supporting the next generation of researchers through a wide range of programming.
Locations
Find your place in our global offices and research labs.
Blog
About
Translating discovery into real-world impact
People
Our researchers drive advancements in computer science through both fundamental and applied research.
Teams
Collaborative groups tackling the world's most challenging AI problems.
Google
Research
Google AI
Learn about all our AI
Google DeepMind
Explore the frontier of AI
Google Labs
Try our AI experiments
Research
Resources
Conferences & events
Careers
Blog
About
Search
Home
Publications
Greedy Column Subset Selection: New Bounds and Distributed Algorithms
Aditya Bhaskara
Afshin Rostamizadeh
Jason Altschuler
Morteza Zadimoghaddam
Thomas Fu
Vahab Mirrokni
ICML (2016) (to appear)
Google Scholar
Copy Bibtex
Abstract
The problem of matrix column subset selection
has recently attracted a large body of research,
with feature selection serving as one obvious and
important application. Among the techniques
that have been applied to solve this problem, the
greedy algorithm has been shown to be quite
effective in practice. However, our theoretical
guarantees on its performance have not been ex-
plored thoroughly, especially in a distributed set-
ting. In this paper, we study the greedy algorithm
for the column subset selection problem from a
theoretical and empirical perspective and show
its effectiveness in a distributed setting. In par-
ticular, we provide an improved approximation
guarantee for the greedy algorithm, and present
the first distributed implementation of this algo-
rithm with provable approximation factors. We
use the idea of randomized composable core-
sets, developed recently in the context of sub-
modular maximization. Finally, we validate the
effectiveness of this distributed algorithm via an
empirical study.
Research Areas
Algorithms and theory
Machine intelligence
Meet the teams driving innovation
Our teams advance the state of the art through research, systems engineering, and collaboration across Google.
See our teams
Follow us
Explore our other initiatives
Google AI
Discover how Google AI is committed to enriching knowledge and solving complex challenges
Products
Build
Research
Responsibility
Societal Impact
About
Google Cloud
High-performance infrastructure for cloud computing, data analytics & machine learning
Overview
Solutions
Products
Pricing
Resources
Google DeepMind
Our mission is to build AI responsibly to benefit humanity
Models
Research
Science
About
Google Labs
Explore the future of AI responsibly with Google Labs
About
Experiments
Stay connected
About Google
Google Products
Privacy
Terms
Cookies management controls
×