research-article

Public Access

Tensor Completion with Nearly Linear Samples Given Weak Side Information

Authors:

Christina Lee Yu,

Xumei XiAuthors Info & Claims

Proceedings of the ACM on Measurement and Analysis of Computing Systems, Volume 6, Issue 2

Article No.: 39, Pages 1 - 35

https://doi.org/10.1145/3530905

Published: 06 June 2022 Publication History

Abstract

Tensor completion exhibits an interesting computational-statistical gap in terms of the number of samples needed to perform tensor estimation. While there are only Θ(tn) degrees of freedom in a t-order tensor with n^t entries, the best known polynomial time algorithm requires O(n^t/2 ) samples in order to guarantee consistent estimation. In this paper, we show that weak side information is sufficient to reduce the sample complexity to O(n). The side information consists of a weight vector for each of the modes which is not orthogonal to any of the latent factors along that mode; this is significantly weaker than assuming noisy knowledge of the subspaces. We provide an algorithm that utilizes this side information to produce a consistent estimator with O(n^1+κ ) samples for any small constant κ > 0. We also provide experiments on both synthetic and real-world datasets that validate our theoretical insights.

References

[1]

Christian Borgs, Jennifer Chayes, Christina E Lee, and Devavrat Shah. Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation. In Advances in Neural Information Processing Systems, pages 4715--4726, 2017.

[2]

Christian Borgs, Jennifer T Chayes, Devavrat Shah, and Christina Lee Yu. Iterative collaborative filtering for sparse matrix estimation. Operations Research, 2021.

[3]

Boaz Barak and Ankur Moitra. Noisy tensor completion via the sum-of-squares hierarchy. In Conference on Learning Theory, 2016.

[4]

1]burkina2021inductiveM Burkina, I Nazarov, M Panov, G Fedonin, and B Shirokikh. Inductive matrix completion with feature selection. Computational Mathematics and Mathematical Physics, 61(5):719--732, 2021.

[5]

Dimitris Bertsimas and Colin Pawlowski. Tensor completion with noisy side information.

[6]

Srinadh Bhojanapalli and Sujay Sanghavi. A new sampling technique for tensors. arXiv preprint arXiv:1502.05023, 2015.

[7]

Stanislav Budzinskiy and Nikolai Zamarashkin. Note: low-rank tensor train completion with side information based on riemannian optimization. arXiv preprint arXiv:2006.12798, 2020.

[8]

Xinyu Chen, Yixian Chen, and Zhaocheng He. Urban traffic speed dataset of guangzhou, china, March 2018.

[9]

Kai-Yang Chiang, Inderjit S Dhillon, and Cho-Jui Hsieh. Using side information to reliably learn low-rank matrices from missing and corrupted observations. The Journal of Machine Learning Research, 19(1):3005--3039, 2018.

Digital Library

[10]

Yuxin Chen, Jianqing Fan, Cong Ma, and Yuling Yan. Inference and uncertainty quantification for noisy matrix completion. Proceedings of the National Academy of Sciences, 116(46):22931--22937, 2019.

[11]

Kai-Yang Chiang, Cho-Jui Hsieh, and Inderjit S Dhillon. Matrix completion with noisy side information. In NIPS, pages 3447--3455, 2015.

Digital Library

[12]

Huiyuan Chen and Jing Li. Collective tensor completion with multiple heterogeneous side information. In 2019 IEEE International Conference on Big Data (Big Data), pages 731--740. IEEE, 2019.

[13]

Changxiao Cai, Gen Li, H Vincent Poor, and Yuxin Chen. Nonconvex low-rank tensor completion from noisy data. Operations Research, 2021.

[14]

Jian-Feng Cai, Lizhang Miao, Yang Wang, and Yin Xian. Provable near-optimal low-multilinear-rank tensor recovery. arXiv preprint arXiv:2007.08904, 2020.

[15]

Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle. A multilinear singular value decomposition. SIAM journal on Matrix Analysis and Applications, 21(4):1253--1278, 2000.

[16]

Shmuel Friedland and Lek-Heng Lim. Nuclear norm of higher-order tensors. arXiv preprint arXiv:1410.6072, 2014.

[17]

Silvia Gandy, Benjamin Recht, and Isao Yamada. Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems, 27(2):025010, 2011.

[18]

Mohsen Ghassemi, Anand Sarwate, and Naveen Goela. Global optimality in inductive matrix completion. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2226--2230. IEEE, 2018.

Digital Library

[19]

Prateek Jain and Inderjit S Dhillon. Provable inductive matrix completion. arXiv preprint arXiv:1306.0626, 2013.

[20]

Prateek Jain and Sewoong Oh. Provable tensor factorization with missing data. In Advances in Neural Information Processing Systems, pages 1431--1439, 2014.

Digital Library

[21]

Misha Elena Kilmer, Karen S. Braman, Ning Hao, and Randy C. Hoover. Third-order tensors as operators on matrices: A theoretical and computational framework with applications in imaging. SIAM J. Matrix Anal. Appl., 34:148--172, 2013.

Digital Library

[22]

Tamara G Kolda. Symmetric orthogonal tensor decomposition is trivial. arXiv preprint arXiv:1503.01375, 2015.

[23]

Ji Liu, Przemyslaw Musialski, Peter Wonka, and Jieping Ye. Tensor completion for estimating missing values in visual data. IEEE transactions on pattern analysis and machine intelligence, 35(1):208--220, 2012.

[24]

Hemank Lamba, Vaishnavh Nagarajan, Kijung Shin, and Naji Shajarisales. Incorporating side information in tensor completion. In Proceedings of the 25th International Conference Companion on World Wide Web, pages 65--66, 2016.

Digital Library

[25]

Yihua Li, Devavrat Shah, Dogyoon Song, and Christina Lee Yu. Nearest neighbors for matrix estimation interpreted as blind regression for latent variable model. IEEE Transactions on Information Theory, 66(3):1760--1784, 2019.

[26]

3]malone2013miriadIan B Malone, David Cash, Gerard R Ridgway, David G MacManus, Sebastien Ourselin, Nick C Fox, and Jonathan M Schott. Miriad-public release of a multiple time point alzheimer's mr imaging dataset. NeuroImage, 70:33--36, 2013.

[27]

Andrea Montanari and Nike Sun. Spectral algorithms for tensor completion. Communications on Pure and Applied Mathematics, 71(11):2381--2425, 2018.

[28]

Atsuhiro Narita, Kohei Hayashi, Ryota Tomioka, and Hisashi Kashima. Tensor factorization using auxiliary information. Data Mining and Knowledge Discovery, 25(2):298--324, 2012.

Digital Library

[29]

Madhav Nimishakavi, Bamdev Mishra, Manish Gupta, and Partha Talukdar. Inductive framework for multi-aspect streaming tensor completion with side information. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pages 307--316, 2018.

Digital Library

[30]

Aaron Potechin and David Steurer. Exact tensor completion with sum-of-squares. arXiv preprint arXiv:1702.06237, 2017.

[31]

Dogyoon Song, Christina E Lee, Yihua Li, and Devavrat Shah. Blind regression: Nonparametric regression for latent variable models via collaborative filtering. In Advances in Neural Information Processing Systems, pages 2155--2163, 2016.

[32]

Devavrat Shah and Christina Lee Yu. Iterative collaborative filtering for sparse noisy tensor estimation. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 41--45. IEEE, 2019.

Digital Library

[33]

Ryota Tomioka, Kohei Hayashi, and Hisashi Kashima. Estimation of low-rank tensors via convex optimization. arXiv preprint arXiv:1010.0789, 2010.

[34]

Ryota Tomioka, Taiji Suzuki, Kohei Hayashi, and Hisashi Kashima. Statistical performance of convex tensor decomposition. In Advances in Neural Information Processing Systems, pages 972--980, 2011.

[35]

Dong Xia and Ming Yuan. On polynomial time methods for exact low-rank tensor completion. Foundations of Computational Mathematics, pages 1--49, 2017.

[36]

Dong Xia, Ming Yuan, and Cun-Hui Zhang. Statistically optimal and computationally efficient low rank tensor completion from noisy entries. arXiv preprint arXiv:1711.04934, 2017.

[37]

Ming Yuan and Cun-Hui Zhang. On tensor completion via nuclear norm minimization. Foundations of Computational Mathematics, 16(4):1031--1068, 2016.

Digital Library

[38]

Ming Yuan and Cun-Hui Zhang. Incoherent tensor norms and their applications in higher order tensor completion. IEEE Transactions on Information Theory, 63(10):6753--6766, 2017.

Digital Library

[39]

Zemin Zhang and Shuchin Aeron. Exact tensor completion using t-svd. IEEE Transactions on Signal Processing, 65(6):1511--1526, 2016.

Digital Library

[40]

4]zhang2014novelZemin Zhang, Gregory Ely, Shuchin Aeron, Ning Hao, and Misha Kilmer. Novel methods for multilinear data completion and de-noising based on tensor-SVD. In 2014 IEEE Conference on Computer Vision and Pattern Recognition, pages 3842--3849, 2014.

Digital Library

[41]

Anru Zhang. Cross: Efficient low-rank tensor completion. Ann. Statist., 47(2):936--964, 04 2019.

[42]

7]zhou2017tensorTengfei Zhou, Hui Qian, Zebang Shen, Chao Zhang, and Congfu Xu. Tensor completion with side information: A riemannian manifold approach. In IJCAI, pages 3539--3545, 2017.

[43]

Dave Zachariah, Martin Sundin, Magnus Jansson, and Saikat Chatterjee. Alternating least-squares for low-rank matrix reconstruction. IEEE Signal Processing Letters, 19(4):231--234, 2012.

Cited By

Lu HLyu FRen JWu HZhou CLiu ZZhang YShen X(2024)CODE$^{+}$+: Fast and Accurate Inference for Compact Distributed IoT Data CollectionIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.345360735:11(2006-2022)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1109/TPDS.2024.3453607
Wang CXie KTian JWen JLi XXie GLi K(2024)HPETC: History Priority Enhanced Tensor Completion for Network Distance MeasurementIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.327430535:6(1012-1028)Online publication date: Jun-2024
https://doi.org/10.1109/TPDS.2023.3274305

Index Terms

Tensor Completion with Nearly Linear Samples Given Weak Side Information
1. Mathematics of computing
  1. Probability and statistics
    1. Statistical paradigms
      1. Dimensionality reduction
2. Theory of computation
  1. Design and analysis of algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Sample complexity and generalization bounds

Recommendations

Tensor Completion with Nearly Linear Samples Given Weak Side Information
SIGMETRICS '22

Tensor completion exhibits an interesting computational-statistical gap in terms of the number of samples needed to perform tensor estimation. While there are only Θ(tn) degrees of freedom in a t-order tensor with nt entries, the best known polynomial ...
Tensor Completion with Nearly Linear Samples Given Weak Side Information
SIGMETRICS/PERFORMANCE '22: Abstract Proceedings of the 2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems

Tensor completion exhibits an interesting computational-statistical gap in terms of the number of samples needed to perform tensor estimation. While there are only Θ(tn) degrees of freedom in a t-order tensor with nt entries, the best known polynomial ...
Sparse and Truncated Nuclear Norm Based Tensor Completion

One of the main difficulties in tensor completion is the calculation of the tensor rank. Recently a tensor nuclear norm, which is equal to the weighted sum of matrix nuclear norms of all unfoldings of the tensor, was proposed to address this issue. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Measurement and Analysis of Computing Systems

Proceedings of the ACM on Measurement and Analysis of Computing Systems Volume 6, Issue 2

POMACS

June 2022

499 pages

EISSN:2476-1249

DOI:10.1145/3543145

Editors:
Augustin Chaintreau
Columbia University
,
Leana Golubchik
University of Southern California
,
Zhi-Li Zhang
University of Minnesota

Issue’s Table of Contents

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2022

Published in POMACS Volume 6, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
223
Total Downloads

Downloads (Last 12 months)96
Downloads (Last 6 weeks)13

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lu HLyu FRen JWu HZhou CLiu ZZhang YShen X(2024)CODE$^{+}$+: Fast and Accurate Inference for Compact Distributed IoT Data CollectionIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.345360735:11(2006-2022)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1109/TPDS.2024.3453607
Wang CXie KTian JWen JLi XXie GLi K(2024)HPETC: History Priority Enhanced Tensor Completion for Network Distance MeasurementIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.327430535:6(1012-1028)Online publication date: Jun-2024
https://doi.org/10.1109/TPDS.2023.3274305

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents