Hybrid linear modeling via local best-fit flats

Teng Zhang; Arthur Szlam; Yi Wang; Gilad Lerman

doi:10.1007/s11263-012-0535-6

Hybrid linear modeling via local best-fit flats

Teng Zhang, Arthur Szlam, Yi Wang, Gilad Lerman

School of Mathematics

Research output: Contribution to journal › Article › peer-review

142 Scopus citations

Abstract

We present a simple and fast geometric method for modeling data by a union of affine subspaces. The method begins by forming a collection of local best-fit affine subspaces, i.e., subspaces approximating the data in local neighborhoods. The correct sizes of the local neighborhoods are determined automatically by the Jones' β ₂ numbers (we prove under certain geometric conditions that our method finds the optimal local neighborhoods). The collection of subspaces is further processed by a greedy selection procedure or a spectral method to generate the final model. We discuss applications to tracking-based motion segmentation and clustering of faces under different illuminating conditions. We give extensive experimental evidence demonstrating the state of the art accuracy and speed of the suggested algorithms on these problems and also on synthetic hybrid linear data as well as the MNIST handwritten digits data; and we demonstrate how to use our algorithms for fast determination of the number of affine subspaces.

Original language	English (US)
Pages (from-to)	217-240
Number of pages	24
Journal	International Journal of Computer Vision
Volume	100
Issue number	3
DOIs	https://doi.org/10.1007/s11263-012-0535-6
State	Published - Dec 2012

Bibliographical note

Funding Information:
Acknowledgements This work was supported by NSF grants DMS-06-12608, DMS-08-11203, DMS-09-15064 and DMS-09-56072. Thanks to the action editor and the reviewers for the careful reading and comments; Peter Jones, Mauro Maggioni and Amit Singer for discussions that motivated our exploration for a multiscale SVD-based HLM algorithm; Ehsan Elhamifar and René Vidal for answering various questions regarding the SSC code and providing us an initial version before the code was available to the public; Allen Yang for clarifying the estimation of the number of clusters in GPCA; and the IMA for a stimulating multi-manifold modeling workshop.

Keywords

Face clustering
High-dimensional data
Hybrid linear modeling
Local PCA
Motion segmentation
Spectral clustering
Subspace clustering

Publisher link

10.1007/s11263-012-0535-6

Find It

Find It at U of M Libraries

Cite this

@article{71653cd163ec4140a136d9749c2f0e86,

title = "Hybrid linear modeling via local best-fit flats",

abstract = "We present a simple and fast geometric method for modeling data by a union of affine subspaces. The method begins by forming a collection of local best-fit affine subspaces, i.e., subspaces approximating the data in local neighborhoods. The correct sizes of the local neighborhoods are determined automatically by the Jones' β 2 numbers (we prove under certain geometric conditions that our method finds the optimal local neighborhoods). The collection of subspaces is further processed by a greedy selection procedure or a spectral method to generate the final model. We discuss applications to tracking-based motion segmentation and clustering of faces under different illuminating conditions. We give extensive experimental evidence demonstrating the state of the art accuracy and speed of the suggested algorithms on these problems and also on synthetic hybrid linear data as well as the MNIST handwritten digits data; and we demonstrate how to use our algorithms for fast determination of the number of affine subspaces.",

keywords = "Face clustering, High-dimensional data, Hybrid linear modeling, Local PCA, Motion segmentation, Spectral clustering, Subspace clustering",

author = "Teng Zhang and Arthur Szlam and Yi Wang and Gilad Lerman",

note = "Funding Information: Acknowledgements This work was supported by NSF grants DMS-06-12608, DMS-08-11203, DMS-09-15064 and DMS-09-56072. Thanks to the action editor and the reviewers for the careful reading and comments; Peter Jones, Mauro Maggioni and Amit Singer for discussions that motivated our exploration for a multiscale SVD-based HLM algorithm; Ehsan Elhamifar and Ren{\'e} Vidal for answering various questions regarding the SSC code and providing us an initial version before the code was available to the public; Allen Yang for clarifying the estimation of the number of clusters in GPCA; and the IMA for a stimulating multi-manifold modeling workshop.",

year = "2012",

month = dec,

doi = "10.1007/s11263-012-0535-6",

language = "English (US)",

volume = "100",

pages = "217--240",

journal = "International Journal of Computer Vision",

issn = "0920-5691",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Hybrid linear modeling via local best-fit flats

AU - Zhang, Teng

AU - Szlam, Arthur

AU - Wang, Yi

AU - Lerman, Gilad

N1 - Funding Information: Acknowledgements This work was supported by NSF grants DMS-06-12608, DMS-08-11203, DMS-09-15064 and DMS-09-56072. Thanks to the action editor and the reviewers for the careful reading and comments; Peter Jones, Mauro Maggioni and Amit Singer for discussions that motivated our exploration for a multiscale SVD-based HLM algorithm; Ehsan Elhamifar and René Vidal for answering various questions regarding the SSC code and providing us an initial version before the code was available to the public; Allen Yang for clarifying the estimation of the number of clusters in GPCA; and the IMA for a stimulating multi-manifold modeling workshop.

PY - 2012/12

Y1 - 2012/12

N2 - We present a simple and fast geometric method for modeling data by a union of affine subspaces. The method begins by forming a collection of local best-fit affine subspaces, i.e., subspaces approximating the data in local neighborhoods. The correct sizes of the local neighborhoods are determined automatically by the Jones' β 2 numbers (we prove under certain geometric conditions that our method finds the optimal local neighborhoods). The collection of subspaces is further processed by a greedy selection procedure or a spectral method to generate the final model. We discuss applications to tracking-based motion segmentation and clustering of faces under different illuminating conditions. We give extensive experimental evidence demonstrating the state of the art accuracy and speed of the suggested algorithms on these problems and also on synthetic hybrid linear data as well as the MNIST handwritten digits data; and we demonstrate how to use our algorithms for fast determination of the number of affine subspaces.

AB - We present a simple and fast geometric method for modeling data by a union of affine subspaces. The method begins by forming a collection of local best-fit affine subspaces, i.e., subspaces approximating the data in local neighborhoods. The correct sizes of the local neighborhoods are determined automatically by the Jones' β 2 numbers (we prove under certain geometric conditions that our method finds the optimal local neighborhoods). The collection of subspaces is further processed by a greedy selection procedure or a spectral method to generate the final model. We discuss applications to tracking-based motion segmentation and clustering of faces under different illuminating conditions. We give extensive experimental evidence demonstrating the state of the art accuracy and speed of the suggested algorithms on these problems and also on synthetic hybrid linear data as well as the MNIST handwritten digits data; and we demonstrate how to use our algorithms for fast determination of the number of affine subspaces.

KW - Face clustering

KW - High-dimensional data

KW - Hybrid linear modeling

KW - Local PCA

KW - Motion segmentation

KW - Spectral clustering

KW - Subspace clustering

UR - http://www.scopus.com/inward/record.url?scp=84867053797&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867053797&partnerID=8YFLogxK

U2 - 10.1007/s11263-012-0535-6

DO - 10.1007/s11263-012-0535-6

M3 - Article

AN - SCOPUS:84867053797

SN - 0920-5691

VL - 100

SP - 217

EP - 240

JO - International Journal of Computer Vision

JF - International Journal of Computer Vision

IS - 3

ER -

Hybrid linear modeling via local best-fit flats

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this