Back to search

University of Minnesota

Modeling data by multiple subspaces: theory and algorithms.

Abstract

dc:description.abstract

We study the problem of modeling data by several affine subspaces, which generalizes the common modeling by a single subspace. It arises, for example, in object tracking and structure from motion. One of the simplest methods for such modeling is based on energy minimization, where the energy involves p-th powers of distances of data points from subspaces. We first analyze under certain assumptions (e.g., spherically symmetric outliers) the effectiveness of such energy minimization for recovering all subspaces simultaneously and also recovering the most significant subspace. We reveal the following phase transition in our setting: when p ≤ 1 the underlying subspaces can be recovered by such energy minimization; whereas when p > 1 the underlying subspaces are sufficiently far from the global minimizer. Nevertheless, for more general settings (i.e., outliers which are not spherically symmetric) we can point at some disadvantages of the energy minimization strategy. In order to practically solve the problem, we present two simple and fast geometric methods for multiple subspaces modeling. One of them minimize energy by gradient descent, and another forms a collection of local best fit affine subspaces, where the size of the local neighborhoods is determined automatically by the Peter Jones beta numbers. This collection of subspaces can then be further processed in various ways. For example, greedy selection procedure according to an appropriate energy or a spectral method to generate the final model. We demonstrate the state of the art accuracy and speed of the suggested procedure on applications for several applications.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhang, Teng

Subjects

dc:subject × 1

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Citation
Zhang, Teng. (2011). Modeling data by multiple subspaces: theory and algorithms.. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/116559.

Chain of custody

source
Harvested from
University of Minnesota
Base URL
conservancy.umn.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Zhang, Teng. Modeling data by multiple subspaces: theory and algorithms.. 2011. http://purl.umn.edu/116559