Efficient point-to-subspace query in ℓ 1 with application to robust face recognition

Ju Sun; Yuqian Zhang; John Wright

doi:10.1007/978-3-642-33765-9_30

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

Ju Sun, Yuqian Zhang, John Wright

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

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 ℓ ¹ distance. We show in theory this problem can be solved with a simple two-stage algorithm: (1) random Cauchy projection of query and subspaces into low-dimensional spaces followed by efficient distance evaluation (ℓ ¹ regression); (2) getting back to the high-dimensional space with very few candidates and performing exhaustive search. We present preliminary experiments on robust face recognition to corroborate our theory.

Original language	English (US)
Title of host publication	Computer Vision, ECCV 2012 - 12th European Conference on Computer Vision, Proceedings
Pages	416-429
Number of pages	14
Edition	PART 4
DOIs	https://doi.org/10.1007/978-3-642-33765-9_30
State	Published - 2012
Externally published	Yes
Event	12th European Conference on Computer Vision, ECCV 2012 - Florence, Italy Duration: Oct 7 2012 → Oct 13 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 4
Volume	7575 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	12th European Conference on Computer Vision, ECCV 2012
Country/Territory	Italy
City	Florence
Period	10/7/12 → 10/13/12

Keywords

Cauchy projection
face recognition
nearest subspace search
subspace modeling
ℓ point-to-subspace distance

Publisher link

10.1007/978-3-642-33765-9_30

Find It

Find It at U of M Libraries

Cite this

Sun, J., Zhang, Y., & Wright, J. (2012). Efficient point-to-subspace query in ℓ ¹ with application to robust face recognition. In Computer Vision, ECCV 2012 - 12th European Conference on Computer Vision, Proceedings (PART 4 ed., pp. 416-429). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7575 LNCS, No. PART 4). https://doi.org/10.1007/978-3-642-33765-9_30

Efficient point-to-subspace query in ℓ ¹ with application to robust face recognition. / Sun, Ju; Zhang, Yuqian; Wright, John.
Computer Vision, ECCV 2012 - 12th European Conference on Computer Vision, Proceedings. PART 4. ed. 2012. p. 416-429 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7575 LNCS, No. PART 4).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sun, J, Zhang, Y & Wright, J 2012, Efficient point-to-subspace query in ℓ ¹ with application to robust face recognition. in Computer Vision, ECCV 2012 - 12th European Conference on Computer Vision, Proceedings. PART 4 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 4, vol. 7575 LNCS, pp. 416-429, 12th European Conference on Computer Vision, ECCV 2012, Florence, Italy, 10/7/12. https://doi.org/10.1007/978-3-642-33765-9_30

Sun J, Zhang Y, Wright J. Efficient point-to-subspace query in ℓ ¹ with application to robust face recognition. In Computer Vision, ECCV 2012 - 12th European Conference on Computer Vision, Proceedings. PART 4 ed. 2012. p. 416-429. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 4). doi: 10.1007/978-3-642-33765-9_30

Sun, Ju ; Zhang, Yuqian ; Wright, John. / Efficient point-to-subspace query in ℓ ¹ with application to robust face recognition. Computer Vision, ECCV 2012 - 12th European Conference on Computer Vision, Proceedings. PART 4. ed. 2012. pp. 416-429 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 4).

@inproceedings{57416ea2dce84d67a3470451c405d3c7,

title = "Efficient point-to-subspace query in ℓ 1 with application to robust face recognition",

abstract = "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. We show in theory this problem can be solved with a simple two-stage algorithm: (1) random Cauchy projection of query and subspaces into low-dimensional spaces followed by efficient distance evaluation (ℓ 1 regression); (2) getting back to the high-dimensional space with very few candidates and performing exhaustive search. We present preliminary experiments on robust face recognition to corroborate our theory.",

keywords = "Cauchy projection, face recognition, nearest subspace search, subspace modeling, ℓ point-to-subspace distance",

author = "Ju Sun and Yuqian Zhang and John Wright",

year = "2012",

doi = "10.1007/978-3-642-33765-9_30",

language = "English (US)",

isbn = "9783642337642",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 4",

pages = "416--429",

booktitle = "Computer Vision, ECCV 2012 - 12th European Conference on Computer Vision, Proceedings",

edition = "PART 4",

note = "12th European Conference on Computer Vision, ECCV 2012 ; Conference date: 07-10-2012 Through 13-10-2012",

}

TY - GEN

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

AU - Sun, Ju

AU - Zhang, Yuqian

AU - Wright, John

PY - 2012

Y1 - 2012

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. We show in theory this problem can be solved with a simple two-stage algorithm: (1) random Cauchy projection of query and subspaces into low-dimensional spaces followed by efficient distance evaluation (ℓ 1 regression); (2) getting back to the high-dimensional space with very few candidates and performing exhaustive search. We present preliminary experiments on robust face recognition to corroborate our theory.

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. We show in theory this problem can be solved with a simple two-stage algorithm: (1) random Cauchy projection of query and subspaces into low-dimensional spaces followed by efficient distance evaluation (ℓ 1 regression); (2) getting back to the high-dimensional space with very few candidates and performing exhaustive search. We present preliminary experiments on robust face recognition to corroborate our theory.

KW - Cauchy projection

KW - face recognition

KW - nearest subspace search

KW - subspace modeling

KW - ℓ point-to-subspace distance

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

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

U2 - 10.1007/978-3-642-33765-9_30

DO - 10.1007/978-3-642-33765-9_30

M3 - Conference contribution

AN - SCOPUS:84867861818

SN - 9783642337642

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 416

EP - 429

BT - Computer Vision, ECCV 2012 - 12th European Conference on Computer Vision, Proceedings

T2 - 12th European Conference on Computer Vision, ECCV 2012

Y2 - 7 October 2012 through 13 October 2012

ER -