## Abstract

In this note, we develop fast and deterministic dimensionality reduction techniques for a family of subspace approximation problems. We then utilize these dimensionality reduction techniques to help rapidly and accurately approximate the n-widths of point sets. Let (Formula presented.) be a given set of M points. The techniques developed herein find an O(nlogM)-dimensional subspace that is guaranteed to always contain a near-best fit n-dimensional hyperplane H for P with respect to the cumulative projection error (Formula presented.), for any chosen p>2. The deterministic algorithm runs in (Formula presented.)-time, and can be randomized to run in only (Formula presented.)-time while maintaining its error guarantees with high probability. In the important p=∞ case, the dimensionality reduction techniques are then combined with efficient algorithms for computing the John ellipsoid of a data set in order to produce an n-dimensional subspace whose maximum ℓ2-distance to any point in the convex hull of P is minimized. The resulting algorithm remains in (Formula presented.)-time.

Original language | English |
---|---|

Pages (from-to) | 281-301 |

Number of pages | 21 |

Journal | Constructive Approximation |

Volume | 42 |

Issue number | 2 |

DOIs | |

State | Published - 4 Oct 2015 |

Externally published | Yes |

## Keywords

- Approximation algorithms
- Dimensionality reduction
- Greedy algorithms
- Least-squares
- Subspace approximation
- n-Widths