License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2018.30
URN: urn:nbn:de:0030-drops-88562
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8856/
Go to the corresponding LIPIcs Volume Portal

Thang, Nguyen Kim

A Greedy Algorithm for Subspace Approximation Problem

pdf-format:
LIPIcs-SWAT-2018-30.pdf (0.3 MB)

Abstract

In the subspace approximation problem, given m points in R^{n} and an integer k <= n, the goal is to find a k-dimension subspace of R^{n} that minimizes the l_{p}-norm of the Euclidean distances to the given points. This problem generalizes several subspace approximation problems and has applications from statistics, machine learning, signal processing to biology. Deshpande et al. [Deshpande et al., 2011] gave a randomized O(sqrt{p})-approximation and this bound is proved to be tight assuming NP != P by Guruswami et al. [Guruswami et al., 2016]. It is an intriguing question of determining the performance guarantee of deterministic algorithms for the problem. In this paper, we present a simple deterministic O(sqrt{p})-approximation algorithm with also a simple analysis. That definitely settles the status of the problem in term of approximation up to a constant factor. Besides, the simplicity of the algorithm makes it practically appealing.

BibTeX - Entry

@InProceedings{thang:LIPIcs:2018:8856,
  author =	{Nguyen Kim Thang},
  title =	{{A Greedy Algorithm for Subspace Approximation Problem}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm  Theory (SWAT 2018)},
  pages =	{30:1--30:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{David Eppstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8856},
  URN =		{urn:nbn:de:0030-drops-88562},
  doi =		{10.4230/LIPIcs.SWAT.2018.30},
  annote =	{Keywords: Approximation Algorithms, Subspace Approximation}
}

Keywords: Approximation Algorithms, Subspace Approximation
Collection: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI