{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T01:36:23Z","timestamp":1777599383320,"version":"3.51.4"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,6,15]],"date-time":"2016-06-15T00:00:00Z","timestamp":1465948800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Basic Research Program of China","doi-asserted-by":"crossref","award":["2013CB336500"],"award-info":[{"award-number":["2013CB336500"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["61222207 and 61233011"],"award-info":[{"award-number":["61222207 and 61233011"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Multimedia Comput. Commun. Appl."],"published-print":{"date-parts":[[2016,6,15]]},"abstract":"<jats:p>\n            Estimating missing entries in matrices has attracted much attention due to its wide range of applications like image inpainting and video denoising, which are usually considered as low-rank matrix completion problems theoretically. It is common to consider nuclear norm as a surrogate of the rank operator since it is the tightest convex lower bound of the rank operator under certain conditions. However, most approaches based on nuclear norm minimization involve a number of singular value decomposition (SVD) operations. Given a matrix\n            <jats:italic>X<\/jats:italic>\n            \u2208 R\n            <jats:sup>\n              <jats:italic>m<\/jats:italic>\n              \u00d7\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            , the time complexity of the SVD operation is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ), which brings prohibitive computational burden on large-scale matrices, limiting the further usage of these methods in real applications. Motivated by this observation, a series of atom-decomposition-based matrix completion methods have been studied. The key to these methods is to reconstruct the target matrix by pursuit methods in a greedy way, which only involves the computation of the top SVD and has great advantages in efficiency compared with the SVD-based matrix completion methods. However, due to gradually serious accumulation errors, atom-decomposition-based methods usually result in unsatisfactory reconstruction accuracy. In this article, we propose a new efficient and scalable atom decomposition algorithm for matrix completion called\n            <jats:italic>Adaptive Basis Selection Strategy<\/jats:italic>\n            (\n            <jats:bold>ABSS<\/jats:bold>\n            ). Different from traditional greedy atom decomposition methods, a two-phase strategy is conducted to generate the basis separately via different strategies according to their different nature. At first, we globally prune the basis space to eliminate the unimportant basis as much as possible and locate the probable subspace containing the most informative basis. Then, another group of basis spaces are learned to improve the recovery accuracy based on local information. In this way, our proposed algorithm breaks through the accuracy bottleneck of traditional atom-decomposition-based matrix completion methods; meanwhile, it reserves the innate efficiency advantages over SVD-based matrix completion methods. We empirically evaluate the proposed algorithm\n            <jats:bold>ABSS<\/jats:bold>\n            on real visual image data and large-scale recommendation datasets. Results have shown that\n            <jats:bold>ABSS<\/jats:bold>\n            has much better reconstruction accuracy with comparable cost to atom-decomposition-based methods. At the same time, it outperforms the state-of-the-art SVD-based matrix completion algorithms by similar or better reconstruction accuracy with enormous advantages on efficiency.\n          <\/jats:p>","DOI":"10.1145\/2903716","type":"journal-article","created":{"date-parts":[[2016,6,15]],"date-time":"2016-06-15T19:32:01Z","timestamp":1466019121000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Atom Decomposition with Adaptive Basis Selection Strategy for Matrix Completion"],"prefix":"10.1145","volume":"12","author":[{"given":"Yao","family":"Hu","sequence":"first","affiliation":[{"name":"State Key Lab of CAD &amp; CG, Zhejiang University, Zhejiang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chen","family":"Zhao","sequence":"additional","affiliation":[{"name":"State Key Lab of CAD &amp; CG, Zhejiang University, Zhejiang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Deng","family":"Cai","sequence":"additional","affiliation":[{"name":"State Key Lab of CAD &amp; CG, Zhejiang University, Zhejiang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaofei","family":"He","sequence":"additional","affiliation":[{"name":"State Key Lab of CAD &amp; CG, Zhejiang University, Zhejiang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuelong","family":"Li","sequence":"additional","affiliation":[{"name":"Center for OPTical IMagery Analysis and Learning (OPTIMAL), State Key Laboratory of Transient Optics and Photonics, Xi'an Institute of Optics and Precision Mechanics, Chinese Academy of Sciences, Shaanxi, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,6,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-007-5040-8"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of KDD Cup and Workshop. 35","author":"Bennett James","year":"2007"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/080738970"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2009.2035722"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2184319.2184343"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2044061"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2393347.2396401"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","volume-title":"Matrix Preconditioning Techniques and Applications","author":"Chen Ke","DOI":"10.1017\/CBO9780511543258"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450037906X"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1864708.1864721"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 15th International Conference on Artificial Intelligence and Statistics-2012 (AISTATS\u201912)","volume":"22","author":"Dudik Miroslav","year":"2012"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of International Conference on Machine Learning. 575--583","author":"Hsieh Cho-Jui","year":"2014"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339581"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2012.271"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88682-2_24"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2010.5539849"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1701495.1701562"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2009.263"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of International Conference on Machine Learning.","author":"Liu Ji","year":"2014"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.526"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.258082"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/604045.604094"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2010.5706969"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1214\/10-AOS850"},{"key":"e_1_2_1_26_1","volume-title":"Conference Record of the 27th Asilomar Conference on Signals, Systems and Computers","author":"Pati Yagyensh Chandra","year":"1993"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2007.383172"},{"key":"e_1_2_1_28_1","volume-title":"Forward-backward greedy algorithms for atomic norm regularization. arXiv preprint arXiv:1404.5692","author":"Rao Nikhil","year":"2014"},{"key":"e_1_2_1_29_1","article-title":"A simpler approach to matrix completion","author":"Recht Benjamin","year":"2011","journal-title":"Journal of Machine Learning Research 12"},{"key":"e_1_2_1_30_1","volume-title":"International Conference on Machine Learning.","author":"Shalev-Shwartz Shai","year":"2011"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2021059"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2013.2278548"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_37"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805766"},{"key":"e_1_2_1_35_1","first-page":"615","article-title":"An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems","volume":"6","author":"Toh Kim-Chuan","year":"2010","journal-title":"Pacific Journal of Optimization"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.909108"},{"key":"e_1_2_1_37_1","unstructured":"R. H. T\u00fct\u00fcnc\u00fc K. C. Toh and M. J. Todd. 2001. SDPT3\u2014a Matlab software package for semidefinite-quadratic-linear programming version 3.0. Retrieved from http:\/\/www.math.nus.edu.sg\/&sim;mattohkc\/sdpt3.html.  R. H. T\u00fct\u00fcnc\u00fc K. C. Toh and M. J. Todd. 2001. SDPT3\u2014a Matlab software package for semidefinite-quadratic-linear programming version 3.0. Retrieved from http:\/\/www.math.nus.edu.sg\/&sim;mattohkc\/sdpt3.html."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 27th International Joint Conference on Artificial Intelligence. AAAI Press, 1764--1770","author":"Wang Shusen","year":"2013"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of International Conference on Machine Learning. 91--99","author":"Wang Zheng","year":"2014"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2009.2016892"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.","author":"Zaid Harchaoui","year":"2012"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2192--2199","author":"Zhang Debing","year":"2012"},{"key":"e_1_2_1_43_1","unstructured":"Tong Zhang. 2009. Adaptive forward-backward greedy algorithm for sparse learning with linear models. In Advances in Neural Information Processing Systems. 1921--1928.  Tong Zhang. 2009. Adaptive forward-backward greedy algorithm for sparse learning with linear models. In Advances in Neural Information Processing Systems. 1921--1928."},{"key":"e_1_2_1_44_1","unstructured":"Xinhua Zhang Dale Schuurmans and Yao-liang Yu. 2012b. Accelerated training for matrix-norm regularization: A boosting approach. In Advances in Neural Information Processing Systems. 2906--2914.  Xinhua Zhang Dale Schuurmans and Yao-liang Yu. 2012b. Accelerated training for matrix-norm regularization: A boosting approach. In Advances in Neural Information Processing Systems. 2906--2914."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277752"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/279232.279236"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2668110"}],"container-title":["ACM Transactions on Multimedia Computing, Communications, and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2903716","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2903716","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:33Z","timestamp":1750222473000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2903716"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,15]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6,15]]}},"alternative-id":["10.1145\/2903716"],"URL":"https:\/\/doi.org\/10.1145\/2903716","relation":{},"ISSN":["1551-6857","1551-6865"],"issn-type":[{"value":"1551-6857","type":"print"},{"value":"1551-6865","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,15]]},"assertion":[{"value":"2015-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}