Efficient point-to-subspace query in ℓ¹ with application to robust object instance recognition

TY - JOUR

T1 - Efficient point-to-subspace query in ℓ1 with application to robust object instance recognition

AU - Sun, Ju

AU - Zhang, Yuqian

AU - Wright, John

N1 - Publisher Copyright: © 2014 Society for Industrial and Applied Mathematics.

PY - 2014/11/6

Y1 - 2014/11/6

N2 - Motivated by vision tasks such as robust face and object recognition, we consider the following general problem: given a collection of low-dimensional linear subspaces in a high-dimensional ambient (image) space, and a query point (image), efficiently determine the nearest subspace to the query in ℓ1 distance. In contrast to the naive exhaustive search which entails large-scale linear programs, we show that the computational burden can be cut down significantly by a simple two-stage algorithm: (1) projecting the query and database subspaces into lower-dimensional space by random Cauchy matrix and solving small-scale distance evaluations (linear programs) in the projection space to locate the nearest candidates; (2) with few candidates upon independent repetition of (1), getting back to the high-dimensional space and performing exhaustive search. To preserve the identity of the nearest subspace with nontrivial probability, the projection dimension typically is a low-order polynomial of the subspace dimension multiplied by a logarithm of the number of the subspaces (Theorem 2.1). The reduced dimensionality and hence complexity render the proposed algorithm particularly relevant to vision applications such as robust face and object instance recognition that we investigate empirically.

AB - Motivated by vision tasks such as robust face and object recognition, we consider the following general problem: given a collection of low-dimensional linear subspaces in a high-dimensional ambient (image) space, and a query point (image), efficiently determine the nearest subspace to the query in ℓ1 distance. In contrast to the naive exhaustive search which entails large-scale linear programs, we show that the computational burden can be cut down significantly by a simple two-stage algorithm: (1) projecting the query and database subspaces into lower-dimensional space by random Cauchy matrix and solving small-scale distance evaluations (linear programs) in the projection space to locate the nearest candidates; (2) with few candidates upon independent repetition of (1), getting back to the high-dimensional space and performing exhaustive search. To preserve the identity of the nearest subspace with nontrivial probability, the projection dimension typically is a low-order polynomial of the subspace dimension multiplied by a logarithm of the number of the subspaces (Theorem 2.1). The reduced dimensionality and hence complexity render the proposed algorithm particularly relevant to vision applications such as robust face and object instance recognition that we investigate empirically.

KW - Cauchy projection

KW - Face recognition

KW - Nearest subspace search

KW - Subspace modeling

KW - ℓ point-to-subspace distance

UR - https://www.scopus.com/pages/publications/84919688094

UR - https://www.scopus.com/pages/publications/84919688094#tab=citedBy

U2 - 10.1137/130936166

DO - 10.1137/130936166

M3 - Article

SN - 1936-4954

VL - 7

SP - 2105

EP - 2138

JO - SIAM Journal on Imaging Sciences

JF - SIAM Journal on Imaging Sciences

IS - 4

ER -