{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:30Z","timestamp":1740109290423,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000646","name":"Japan Society for the Promotion of Science London","doi-asserted-by":"publisher","award":["JP17H04676"],"award-info":[{"award-number":["JP17H04676"]}],"id":[{"id":"10.13039\/501100000646","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,5]]},"DOI":"10.1007\/s00453-019-00642-0","type":"journal-article","created":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T22:37:06Z","timestamp":1572043026000},"page":"1277-1297","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Testing Proximity to Subspaces: Approximate $$\\ell _\\infty $$\u00a0Minimization in Constant Time"],"prefix":"10.1007","volume":"82","author":[{"given":"Kohei","family":"Hayashi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8919-8479","authenticated-orcid":false,"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,25]]},"reference":[{"issue":"4","key":"642_CR1","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","volume":"66","author":"D Achlioptas","year":"2003","unstructured":"Achlioptas, D.: Database-friendly random projections: Johnson\u2013Lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4), 671\u2013687 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"642_CR2","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1137\/S0895480102410973","volume":"16","author":"N Alon","year":"2003","unstructured":"Alon, N., Dar, S., Parnas, M., Ron, D.: Testing of clustering. SIAM J. Discrete Math. 16(3), 393\u2013417 (2003)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"642_CR3","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/060667177","volume":"39","author":"N Alon","year":"2009","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: It\u2019s all about regularity. SIAM J. Comput. 39(1), 143\u2013167 (2009)","journal-title":"SIAM J. Comput."},{"key":"642_CR4","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1137\/1.9781611975482.46","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Maria-Florina Balcan","year":"2019","unstructured":"Balcan, M.-F., Li, Y., Woodruff, D.P., Zhang, H.: Testing matrix rank, optimally. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 727\u2013746 (2019)"},{"issue":"3","key":"642_CR5","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1145\/355644.355651","volume":"1","author":"I Barrodale","year":"1975","unstructured":"Barrodale, I., Phillips, C.: Algorithm 495: solution of an overdetermined system of linear equations in the chebychev norm [F4]. ACM Trans. Math. Softw. 1(3), 264\u2013270 (1975)","journal-title":"ACM Trans. Math. Softw."},{"key":"642_CR6","doi-asserted-by":"crossref","unstructured":"Bingham, E., Mannila, H.: Random projection in dimensionality reduction: applications to image and text data. In: Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 245\u2013250 (2001)","DOI":"10.1145\/502512.502546"},{"key":"642_CR7","doi-asserted-by":"crossref","unstructured":"Borgs, C., Chayes, J., Lov\u00e1sz, L., S\u00f3s, V.T., Szegedy, B., Vesztergombi, K.: Graph limits and parameter testing. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 261\u2013270 (2006)","DOI":"10.1145\/1132516.1132556"},{"issue":"3","key":"642_CR8","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/BF02310791","volume":"35","author":"JD Carroll","year":"1970","unstructured":"Carroll, J.D., Chang, J.-J.: Analysis of individual differences in multidimensional scaling via an $$N$$-way generalization of \u201cEckart\u2013Young\u201d decomposition. Psychometrika 35(3), 283\u2013319 (1970)","journal-title":"Psychometrika"},{"key":"642_CR9","unstructured":"Chandrasekaran, K., Cheraghchi, M., Gandikota, V., Grigorescu, E.: Local testing for membership in lattices. In: Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 46:1\u201346:14 (2016)"},{"issue":"2","key":"642_CR10","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"KL Clarkson","year":"1995","unstructured":"Clarkson, K.L.: Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42(2), 488\u2013499 (1995)","journal-title":"J. ACM"},{"issue":"6","key":"642_CR11","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1002\/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9","volume":"41","author":"S Deerwester","year":"1990","unstructured":"Deerwester, S., Dumais, S., Furnas, G., Landauer, T., Harshman, R.: Indexing by latent semantic analysis. J. Am. Soc. Inf. Sci. 41(6), 391\u2013407 (1990)","journal-title":"J. Am. Soc. Inf. Sci."},{"issue":"3","key":"642_CR12","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1109\/3468.759273","volume":"29","author":"H Ding","year":"1999","unstructured":"Ding, H., Wang, J.: Recurrent neural networks for minimum infinity-norm kinematic control of redundant manipulators. IEEE Trans. Syst. Man Cybern. Part A 29(3), 269\u2013276 (1999)","journal-title":"IEEE Trans. Syst. Man Cybern. Part A"},{"issue":"4","key":"642_CR13","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/S0167-9473(96)00071-0","volume":"24","author":"RW Farebrother","year":"1997","unstructured":"Farebrother, R.W.: The historical development of the linear minimax absolute residual estimation procedure 1786\u20131960. Comput. Stat. Data Anal. 24(4), 455\u2013466 (1997)","journal-title":"Comput. Stat. Data Anal."},{"issue":"2","key":"642_CR14","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","volume":"32","author":"O Goldreich","year":"2002","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica 32(2), 302\u2013343 (2002)","journal-title":"Algorithmica"},{"key":"642_CR15","unstructured":"Guestrin, C., Koller, D., Parr, R.: Max-norm projections for factored MDPs. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI), pp. 673\u2013680 (2001)"},{"key":"642_CR16","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/173","volume-title":"Geometric Approximation Algorithms","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. American Mathematical Society, Providence (2011)"},{"key":"642_CR17","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1109\/36.298007","volume":"32","author":"JC Harsanyi","year":"1994","unstructured":"Harsanyi, J.C., Chang, C.-I.: Hyperspectral image classification and dimensionality reduction: an orthogonal subspace projection approach. IEEE Trans. Geosci. Remote Sens. 32, 779\u2013785 (1994)","journal-title":"IEEE Trans. Geosci. Remote Sens."},{"key":"642_CR18","unstructured":"Harshman, R.: Foundations of the parafac procedure: models and conditions for an \u201cexplanatory\u201d multi-modal factor analysis. UCLA Working Papers in Phonetics, p. 16 (1970)"},{"key":"642_CR19","doi-asserted-by":"crossref","unstructured":"Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. In: Proceedings of the 2nd Annual Symposium on Computational geometry (SoCG), pp. 61\u201371 (1986)","DOI":"10.1145\/10515.10522"},{"key":"642_CR20","unstructured":"Hayashi, K., Yoshida, Y.: Minimizing quadratic functions in constant time. In: Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS), pp. 2217\u20132225 (2016)"},{"key":"642_CR21","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1037\/h0071325","volume":"24","author":"H Hotelling","year":"1933","unstructured":"Hotelling, H.: Analysis of a complex of statistical variables into principal components. J. Educ. Psychol. 24, 417\u2013441 (1933)","journal-title":"J. Educ. Psychol."},{"key":"642_CR22","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1198\/004017004000000563","volume":"47","author":"M Hubert","year":"2005","unstructured":"Hubert, M., Rousseeuw, P., Vanden Branden, K.: ROBPCA: a new approach to robust principal component analysis. Technometrics 47, 64\u201379 (2005)","journal-title":"Technometrics"},{"issue":"9","key":"642_CR23","doi-asserted-by":"publisher","first-page":"1603","DOI":"10.1109\/TPAMI.2007.70824","volume":"30","author":"F Kahl","year":"2008","unstructured":"Kahl, F., Hartley, R.: Multiple-view geometry under the $$L_\\infty $$-norm. IEEE Trans. Pattern Anal. Mach. Intell. 30(9), 1603\u20131617 (2008)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"642_CR24","unstructured":"Krauthgamer, R., Sasson, O.: Property testing of data dimensionality. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 18\u201327 (2003)"},{"key":"642_CR25","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 296\u2013303 (2014)","DOI":"10.1145\/2608628.2608664"},{"key":"642_CR26","doi-asserted-by":"publisher","first-page":"2278","DOI":"10.1109\/5.726791","volume":"86","author":"Y LeCun","year":"1998","unstructured":"LeCun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proc. IEEE 86, 2278\u20132324 (1998)","journal-title":"Proc. IEEE"},{"issue":"6755","key":"642_CR27","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1038\/44565","volume":"401","author":"DD Lee","year":"1999","unstructured":"Lee, D.D., Seung, H.S.: Learning the parts of objects by non-negative matrix factorization. Nature 401(6755), 788\u2013791 (1999)","journal-title":"Nature"},{"key":"642_CR28","doi-asserted-by":"crossref","unstructured":"Li, Y., Wang, Z., Woodruff, D.P.: Improved testing of low rank matrices. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 691\u2013700 (2014)","DOI":"10.1145\/2623330.2623736"},{"key":"642_CR29","unstructured":"Mart\u00ednez, A., Benavente, R.: The AR face database. Technical report\u00a024, Computer Vision Center (1998)"},{"key":"642_CR30","series-title":"Arkiv f\u00f6r matematik, astronomi och fysik","volume-title":"Sur l\u2019Approximation du d\u00e9terminant de Fredholm par les d\u00e9terminants des syst\u00e8mes d\u2019\u00e9quations lin\u00e9aires","author":"A Ostrowski","year":"1938","unstructured":"Ostrowski, A.: Sur l\u2019Approximation du d\u00e9terminant de Fredholm par les d\u00e9terminants des syst\u00e8mes d\u2019\u00e9quations lin\u00e9aires. Arkiv f\u00f6r matematik, astronomi och fysik. Almqvist & Wiksells, Stockholm (1938)"},{"key":"642_CR31","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1080\/14786440109462720","volume":"2","author":"K Pearson","year":"1901","unstructured":"Pearson, K.: On lines and planes of closest fit to systems of points in space. Philos. Mag. 2, 559\u2013572 (1901)","journal-title":"Philos. Mag."},{"issue":"3","key":"642_CR32","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1137\/1006061","volume":"6","author":"JR Rice","year":"1964","unstructured":"Rice, J.R., White, J.S.: Norms for smoothing and estimation. SIAM Rev. 6(3), 243\u2013256 (1964)","journal-title":"SIAM Rev."},{"issue":"2","key":"642_CR33","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"key":"642_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01386203","volume":"2","author":"E Stiefel","year":"1960","unstructured":"Stiefel, E.: Note on Jordan elimination, linear programming and Tschebyscheff approximation. Numer. Math. 2, 1\u201317 (1960)","journal-title":"Numer. Math."},{"issue":"6","key":"642_CR35","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1137\/0914076","volume":"14","author":"AJ Stromberg","year":"1993","unstructured":"Stromberg, A.J.: Computing the exact least median of squares estimate and stability diagnostics in multiple linear regression. SIAM J. Sci. Comput. 14(6), 1289\u20131299 (1993)","journal-title":"SIAM J. Sci. Comput."},{"key":"642_CR36","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/BF02288916","volume":"17","author":"WS Torgerson","year":"1952","unstructured":"Torgerson, W.S.: Multidimensional scaling: I. Theory and method. Psychometrika 17, 401\u2013419 (1952)","journal-title":"Psychometrika"},{"issue":"2","key":"642_CR37","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1214\/aoms\/1177698963","volume":"38","author":"M Woodroofe","year":"1967","unstructured":"Woodroofe, M.: On the maximum deviation of the sample density. Ann. Math. Stat. 38(2), 475\u2013481 (1967)","journal-title":"Ann. Math. Stat."},{"key":"642_CR38","doi-asserted-by":"crossref","unstructured":"Yoshida, Y.: A characterization of locally testable affine-invariant properties via decomposition theorems. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pp. 154\u2013163 (2014)","DOI":"10.1145\/2591796.2591802"},{"key":"642_CR39","doi-asserted-by":"crossref","unstructured":"Yoshida, Y.: Gowers norm, function limits, and parameter estimation. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1391\u20131406 (2016)","DOI":"10.1137\/1.9781611974331.ch96"},{"issue":"2","key":"642_CR40","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1214\/aos\/1176349146","volume":"21","author":"B Yu","year":"1993","unstructured":"Yu, B.: Density estimation in the $$l^\\infty $$ norm for dependent data with applications to the Gibbs sampler. Ann. Stat. 21(2), 711\u2013735 (1993)","journal-title":"Ann. Stat."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00642-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00642-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00642-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T23:06:48Z","timestamp":1603494408000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00642-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,25]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["642"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00642-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,10,25]]},"assertion":[{"value":"19 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}