IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v84y2022i1d10.1007_s10898-022-01140-4.html
   My bibliography  Save this article

Several approximation algorithms for sparse best rank-1 approximation to higher-order tensors

Author

Listed:
  • Xianpeng Mao

    (Guangxi University)

  • Yuning Yang

    (Guangxi University)

Abstract

Sparse tensor best rank-1 approximation (BR1Approx), which is a sparsity generalization of the dense tensor BR1Approx, and is a higher-order extension of the sparse matrix BR1Approx, is one of the most important problems in sparse tensor decomposition and related problems arising from statistics and machine learning. By exploiting the multilinearity as well as the sparsity structure of the problem, four polynomial-time approximation algorithms are proposed, which are easily implemented, of low computational complexity, and can serve as initial procedures for iterative algorithms. In addition, theoretically guaranteed approximation lower bounds are derived for all the algorithms. We provide numerical experiments on synthetic and real data to illustrate the efficiency and effectiveness of the proposed algorithms; in particular, serving as initialization procedures, the approximation algorithms can help in improving the solution quality of iterative algorithms while reducing the computational time.

Suggested Citation

  • Xianpeng Mao & Yuning Yang, 2022. "Several approximation algorithms for sparse best rank-1 approximation to higher-order tensors," Journal of Global Optimization, Springer, vol. 84(1), pages 229-253, September.
    • Handle: RePEc:spr:jglopt:v:84:y:2022:i:1:d:10.1007_s10898-022-01140-4
    DOI: 10.1007/s10898-022-01140-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-022-01140-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-022-01140-4?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Will Wei Sun & Lexin Li, 2019. "Dynamic Tensor Clustering," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 114(528), pages 1894-1907, October.
    2. Will Wei Sun & Junwei Lu & Han Liu & Guang Cheng, 2017. "Provable sparse tensor decomposition," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 79(3), pages 899-916, June.
    3. Simai He & Bo Jiang & Zhening Li & Shuzhong Zhang, 2014. "Probability Bounds for Polynomial Functions in Random Variables," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 889-907, August.
    4. Anru Zhang & Rungang Han, 2019. "Optimal Sparse Singular Value Decomposition for High-Dimensional High-Order Data," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 114(528), pages 1708-1725, October.
    5. Junhui Wang, 2010. "Consistent selection of the number of clusters via crossvalidation," Biometrika, Biometrika Trust, vol. 97(4), pages 893-904.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Mao, Xianpeng & Yang, Yuning, 2022. "Best sparse rank-1 approximation to higher-order tensors via a truncated exponential induced regularizer," Applied Mathematics and Computation, Elsevier, vol. 433(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mao, Xianpeng & Yang, Yuning, 2022. "Best sparse rank-1 approximation to higher-order tensors via a truncated exponential induced regularizer," Applied Mathematics and Computation, Elsevier, vol. 433(C).
    2. Han Yu & Brian Chapman & Arianna Di Florio & Ellen Eischen & David Gotz & Mathews Jacob & Rachael Hageman Blair, 2019. "Bootstrapping estimates of stability for clusters, observations and model selection," Computational Statistics, Springer, vol. 34(1), pages 349-372, March.
    3. Shi, Chengchun & Lu, Wenbin & Song, Rui, 2019. "Determining the number of latent factors in statistical multi-relational learning," LSE Research Online Documents on Economics 102110, London School of Economics and Political Science, LSE Library.
    4. Bilian Chen & Zhening Li, 2020. "On the tensor spectral p-norm and its dual norm via partitions," Computational Optimization and Applications, Springer, vol. 75(3), pages 609-628, April.
    5. Yuning Yang, 2022. "On Approximation Algorithm for Orthogonal Low-Rank Tensor Approximation," Journal of Optimization Theory and Applications, Springer, vol. 194(3), pages 821-851, September.
    6. Yuefeng Han & Cun-Hui Zhang & Rong Chen, 2021. "CP Factor Model for Dynamic Tensors," Papers 2110.15517, arXiv.org.
    7. Carlos Martin-Barreiro & John A. Ramirez-Figueroa & Ana B. Nieto-Librero & Víctor Leiva & Ana Martin-Casado & M. Purificación Galindo-Villardón, 2021. "A New Algorithm for Computing Disjoint Orthogonal Components in the Three-Way Tucker Model," Mathematics, MDPI, vol. 9(3), pages 1-22, January.
    8. Paul, Biplab & De, Shyamal K. & Ghosh, Anil K., 2022. "Some clustering-based exact distribution-free k-sample tests applicable to high dimension, low sample size data," Journal of Multivariate Analysis, Elsevier, vol. 190(C).
    9. Minjie Wang & Tianyi Yao & Genevera I. Allen, 2023. "Supervised convex clustering," Biometrics, The International Biometric Society, vol. 79(4), pages 3846-3858, December.
    10. Jiangtao Duan & Wei Gao & Hao Qu & Hon Keung Tony, 2019. "Subspace Clustering for Panel Data with Interactive Effects," Papers 1909.09928, arXiv.org, revised Feb 2021.
    11. Rozmus Dorota, 2020. "Clustering Poland Among Eu Countries in Terms of a Sustainable Development Level in the Light of Various Cluster Stability Measures," Folia Oeconomica Stetinensia, Sciendo, vol. 20(1), pages 319-340, June.
    12. Rungang Han & Yuetian Luo & Miaoyan Wang & Anru R. Zhang, 2022. "Exact clustering in tensor block model: Statistical optimality and computational limit," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 84(5), pages 1666-1698, November.
    13. Li, Gen, 2020. "Generalized Co-clustering Analysis via Regularized Alternating Least Squares," Computational Statistics & Data Analysis, Elsevier, vol. 150(C).
    14. Victoria Gregory & Guido Menzio & David Wiczer, 2021. "The Alpha Beta Gamma of the Labor Market," Working Papers 2021-003, Federal Reserve Bank of St. Louis, revised Sep 2022.
    15. Dario Cottafava & Giulia Sonetti & Paolo Gambino & Andrea Tartaglino, 2018. "Explorative Multidimensional Analysis for Energy Efficiency: DataViz versus Clustering Algorithms," Energies, MDPI, vol. 11(5), pages 1-18, May.
    16. Kai Deng & Xin Zhang, 2022. "Tensor envelope mixture model for simultaneous clustering and multiway dimension reduction," Biometrics, The International Biometric Society, vol. 78(3), pages 1067-1079, September.
    17. Zhang, Tonglin & Lin, Ge, 2021. "Generalized k-means in GLMs with applications to the outbreak of COVID-19 in the United States," Computational Statistics & Data Analysis, Elsevier, vol. 159(C).
    18. Will Wei Sun & Xingye Qiao & Guang Cheng, 2016. "Stabilized Nearest Neighbor Classifier and its Statistical Properties," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 111(515), pages 1254-1265, July.
    19. Chang, Jinyuan & Zhang, Henry & Yang, Lin & Yao, Qiwei, 2023. "Modelling matrix time series via a tensor CP-decomposition," LSE Research Online Documents on Economics 117644, London School of Economics and Political Science, LSE Library.
    20. Jonas M. B. Haslbeck & Dirk U. Wulff, 2020. "Estimating the number of clusters via a corrected clustering instability," Computational Statistics, Springer, vol. 35(4), pages 1879-1894, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:84:y:2022:i:1:d:10.1007_s10898-022-01140-4. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.