{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T19:55:14Z","timestamp":1790884514837,"version":"4.1.0"},"reference-count":56,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We study the following problem of subset selection for matrices: given a matrix $\\mathbf{X} \\in \\mathbb{R}^{n \\times m}$ ($m &gt; n$) and a sampling parameter $k$ ($n \\le k \\le m$), select a subset of $k$ columns from $\\mathbf{X}$ such that the pseudoinverse of the sampled matrix has as small a norm as possible. In this work, we focus on the Frobenius and the spectral matrix norms. We describe several novel (deterministic and randomized) approximation algorithms for this problem with approximation bounds that are optimal up to constant factors. Additionally, we show that the combinatorial problem of finding a low-stretch spanning tree in an undirected graph corresponds to subset selection, and discuss various implications of this reduction.<\/jats:p>","DOI":"10.1137\/120867287","type":"journal-article","created":{"date-parts":[[2013,10,30]],"date-time":"2013-10-30T12:20:06Z","timestamp":1383135606000},"page":"1464-1499","source":"Crossref","is-referenced-by-count":62,"title":["Faster Subset Selection for Matrices and Applications"],"prefix":"10.1137","volume":"34","author":[{"given":"Haim","family":"Avron","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Boutsidis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,10,30]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"I. Abraham, Y. Bartal, and O. Neiman,\n                      Nearly tight low stretch spanning trees\n                      , in Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS), 2008, pp. 781-790.","DOI":"10.1109\/FOCS.2008.62"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/090767911"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"J. Batson, D. Spielman, and N. Srivastava,\n                      Twice-Ramanujan sparsifiers\n                      , in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, pp. 255-262, 2009.","DOI":"10.1145\/1536414.1536451"},{"key":"atypb5","unstructured":"D. S. Bernstein,\n                      Matrix Mathematics: Theory, Facts, and Formulas with Applications to Linear Systems Theory\n                      , Princeton University Press, Princeton, NJ, 2005."},{"key":"atypb6","unstructured":"E. G. Boman and B. Hendrickson,\n                      On Spanning Tree Preconditioners\n                      , Sandia National Laboratories, Albuquerque, NM, unpublished manuscript, 2001."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772174"},{"key":"atypb9","unstructured":"C. Boutsidis,\n                      Topics in matrix sampling algorithms\n                      , Ph.D. thesis, Rensselaer Polytechnic Institute, May, 2011."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"C. Boutsidis, P. Drineas, and M. Magdon-Ismail,\n                      Near optimal column based matrix reconstruction\n                      , in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, Los Alamitos, CA, 2011, pp. 305-314. Full version available online at http:\/\/arxiv.org\/pdf\/1103.0995v2.pdf.","DOI":"10.1109\/FOCS.2011.21"},{"key":"atypb11","unstructured":"C. Boutsidis and M. Magdon-Ismail,\n                      Deterministic feature selection for $k$-means clustering\n                      , arxiv: 1109.5664, 2011."},{"key":"atypb12","first-page":"968","author":"Boutsidis C.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb13","unstructured":"C. Boutsidis, A. Zouzias, M. W. Mahoney, and P. Drineas,\n                      Stochastic dimensionality reduction for $k$-means clustering\n                      , arxiv: 1110.2897, 2013."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/09S010435"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/0913043"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1680010105"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9582-6"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.018"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.08.034"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2010.11.053"},{"key":"atypb21","first-page":"329","author":"Deshpande A.","year":"2010","journal-title":"New York"},{"key":"atypb22","first-page":"1117","author":"Deshpande A.","year":"2006","journal-title":"New York"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442684"},{"key":"atypb24","unstructured":"P. Drineas, M. Magdon-Ismail, M. W. Mahoney, and D. P. Woodruff,\n                      Fast approximation of matrix coherence and statistical leverage\n                      , 13 (2012), pp. 3475-3506."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-010-0331-6"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/0732088"},{"key":"atypb27","first-page":"494","author":"Elkin M.","year":"2005","journal-title":"New York"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/1132973.1132981"},{"key":"atypb29","unstructured":"A. Gittens,\n                      The spectral norm error of the naive Nystrom extension\n                      , arXiv:1110.5305, 2011."},{"key":"atypb30","unstructured":"G. Golub and C. V. Loan,\n                      Matrix Computations\n                      , Johns Hopkins University Press, 3rd ed., Baltimore, 1996."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(96)00301-1"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479893251472"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/0917055"},{"key":"atypb34","first-page":"76","volume":"17","author":"Gu M.","year":"2004","journal-title":"Electron. Trans. Numer. Anal."},{"key":"atypb35","first-page":"1207","author":"Guruswami V.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01937276"},{"key":"atypb37","first-page":"213","volume":"58","author":"Hong Y. P.","year":"1992","journal-title":"Math. Comput."},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"R. Horn and C. Johnson,\n                      Matrix Analysis\n                      , Cambridge University Press, New York, 1985.","DOI":"10.1017\/CBO9780511810817"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/090780882"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2008.2007095"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.05.006"},{"key":"atypb42","unstructured":"I. Koutis, G. L. Miller, and R. Peng,\n                      Solving SDD linear systems in time $\\tilde{O}(m\\log{n}\\log(1\/\\epsilon))$\n                      , in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2011."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2010.02.003"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-0745-8"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(00)00120-8"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"D. Peleg,\n                      Distributed Computing: A Locality-Sensitive Approach\n                      , SIAM, Philadelphia, 2000.","DOI":"10.1137\/1.9780898719772"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255449"},{"key":"atypb48","first-page":"143","author":"Sarl\u00f3s T.","year":"2006","journal-title":"Washington, DC"},{"key":"atypb49","first-page":"563","author":"Spielman D. A.","year":"2008","journal-title":"New York"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-011-0194-2"},{"key":"atypb51","first-page":"81","author":"Spielman D. A.","year":"2004","journal-title":"New York"},{"key":"atypb52","unstructured":"D. A. Spielman and J. Woo,\n                      A note on preconditioning by low-stretch spanning trees\n                      , arXiv:0903.2816, 2009."},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1142\/S1793536911000787"},{"key":"atypb54","first-page":"978","author":"Tropp J. A.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb55","unstructured":"R. Vershynin,\n                      A Note on Sums of Independent Random Matrices after Ahlswede-Winter\n                      , Lecture Notes, 2010, available online at http:\/\/www-personal.umich.edu\/$\\sim$romanv\/teaching\/ reading-group\/ahlswede-winter.pdf."},{"key":"atypb56","first-page":"296","author":"Wilson D. B.","year":"1996","journal-title":"New York"},{"key":"atypb57","doi-asserted-by":"crossref","unstructured":"A. Zouzias,\n                      A matrix hyperbolic cosine algorithm and applications\n                      , arXiv:1103.2793, 2011.","DOI":"10.1007\/978-3-642-31594-7_71"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120867287","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:38:40Z","timestamp":1787330320000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120867287"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/120867287"],"URL":"https:\/\/doi.org\/10.1137\/120867287","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}