{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T20:28:34Z","timestamp":1791145714990,"version":"4.1.0"},"reference-count":47,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Imaging Sci."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>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 $\\ell^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.<\/jats:p>","DOI":"10.1137\/130936166","type":"journal-article","created":{"date-parts":[[2014,11,6]],"date-time":"2014-11-06T11:26:11Z","timestamp":1415273171000},"page":"2105-2138","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Point-to-Subspace Query in $\\ell^1$ with Application to Robust Object Instance Recognition"],"prefix":"10.1137","volume":"7","author":[{"given":"Ju","family":"Sun","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuqian","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Wright","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,11,6]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOS1032"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.33"},{"key":"atypb3","first-page":"1","author":"Basri R.","year":"2007","journal-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.110"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1177153"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1227983"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, UK, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089026"},{"key":"atypb10","unstructured":"E. Cande\u0300s and J. Romberg,\n                      $\\ell^1$-Magic: Recovery of Sparse Signals via Convex Programming\n                      , http:\/\/users.ece.gatech.edu\/justin\/l1magic\/downloads\/l1magic.pdf (2005)."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.34"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1109\/34.927467"},{"key":"atypb14","first-page":"932","author":"Dasgupta A.","year":"2008","journal-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10073"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"atypb17","first-page":"1190","author":"Do Ba K.","year":"2010","journal-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-005-4965-4"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.929958"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1214\/009053604000000067"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.visres.2010.01.002"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/34.927464"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000042993.50813.60"},{"key":"atypb24","unstructured":"B. V. Gnedenko and A. N. Kolmogorov,\n                      Limit Distributions for Sums of Independent Random Variables\n                      , Addison-Wesley, Reading, MA, 1968."},{"key":"atypb25","first-page":"11","author":"Ho J.","year":"2003","journal-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.121"},{"key":"atypb27","first-page":"189","author":"Johnson W. B","year":"1984","journal-title":"RI"},{"key":"atypb28","unstructured":"M. Ledoux,\n                      The Concentration of Measure Phenomenon\n                      , AMS, Providence, RI, 2001."},{"key":"atypb29","first-page":"2497","volume":"8","author":"Li P.","year":"2007","journal-title":"J. Mach. Learn. Res."},{"key":"atypb30","first-page":"523","author":"Magen A.","year":"2008","journal-title":"Berlin"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s11081-011-9176-9"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01421486"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.4"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1126\/science.290.5500.2323"},{"key":"atypb35","first-page":"239","author":"Simard P.","year":"1998","journal-title":"Berlin"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"C. Sohler and D. P. Woodruff,\n                      Subspace embeddings for the $\\ell_1$-norm with applications\n                      , in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 2011, pp. 755-764.","DOI":"10.1145\/1993636.1993736"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1162\/jocn.1991.3.1.71"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"V. V. Uchaikin and V. M. Zolotarev,\n                      Chance and Stability: Stable Distributions and Their Applications\n                      , Vol. 3, VSP, Utrecht, The Netherlands, 1999.","DOI":"10.1515\/9783110935974"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2011.112"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2048473"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.79"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"A. Yang, A. Ganesh, Y. Ma, and S. Sastry,\n                      Fast $\\ell^1$-minimization algorithms and an application in robust face recognition: A review\n                      , in Proceedings of the International Conference on Image Processing, 2010.","DOI":"10.1109\/ICIP.2010.5651522"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2013.2262292"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1137\/070703983"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"Y. Zhang, C. Mu, H. Kuo, and J. Wright,\n                      Towards guaranteed illumination models for nonconvex objects\n                      , in Proceedings of the International Conference on Computer Vision, 2013.","DOI":"10.1109\/ICCV.2013.120"},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"V.M. Zolotarev,\n                      One-Dimensional Stable Distributions\n                      , Transl. Math. Monogr. 65, AMS, Providence, RI, 1986.","DOI":"10.1090\/mmono\/065"}],"container-title":["SIAM Journal on Imaging Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130936166","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:14:12Z","timestamp":1787318052000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130936166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/130936166"],"URL":"https:\/\/doi.org\/10.1137\/130936166","relation":{},"ISSN":["1936-4954"],"issn-type":[{"value":"1936-4954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}