Efficient frequent directions algorithms for approximate decomposition of matrices and higher-order tensors

Maolin Che; Yimin Wei; Hong Yan

Efficient frequent directions algorithms for approximate decomposition of matrices and higher-order tensors

Maolin Che, Yimin Wei, Hong Yan

Department of Electrical Engineering

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

1 Downloads (CityUHK Scholars)

Abstract

In the framework of the FD (frequent directions) algorithm, we first develop two efficient algorithms for low-rank matrix approximations under the embedding matrices composed of the product of any SpEmb (sparse embedding) matrix and any standard Gaussian matrix, or any SpEmb matrix and any SRHT (subsampled randomized Hadamard transform) matrix. The theoretical results are also achieved based on the bounds of singular values of standard Gaussian matrices and the theoretical results for SpEmb and SRHT matrices. With a given Tucker-rank, we then obtain several efficient FD-based randomized variants of T-HOSVD (the truncated high-order singular value decomposition) and ST-HOSVD (sequentially T-HOSVD), which are two common algorithms for computing the approximate Tucker decomposition of any tensor with a given Tucker-rank. We also consider efficient FD-based randomized algorithms for computing the approximate TT (tensor-train) decomposition of any tensor with a given TT-rank. Finally, we illustrate the efficiency and accuracy of these algorithms using synthetic and real-world matrix (and tensor) data. ©2026 Maolin Che, Yimin Wei and Hong Yan.

Original language	English
Pages (from-to)	1-56
Journal	Journal of Machine Learning Research
Volume	27
Issue number	3
Publication status	Published - Feb 2026

Funding

The authors would like to thank the Action Editor Professor Animashree Anandkumar and three anonymous reviewers for their careful and very detailed comments on our paper. This work is supported by the Natural Science Special Project Research Fund of Guizhou University (No. 2025-06), the Hong Kong Innovation and Technology Commission (InnoHK Project CIMDA), the Hong Kong Research Grants Council (Project 11204821), City University of Hong Kong (Projects 9610034 and 9610460) and the National Natural Science Foundation of China under the grant 12561095, 12271108 and U24A2001.

Research Keywords

approximate TT decomposition
approximate Tucker decomposition
classification
frequent directions
Low-rank approximation
random projection
randomized algorithms
sparse embedding matrices
ST-HOSVD
standard Gaussian matrices
subsampled randomized Hadamard transform
T-HOSVD
TT-SVD

Publisher's Copyright Statement

This full text is made available under CC-BY 4.0. https://creativecommons.org/licenses/by/4.0/

Access Output

450649510.pdfFinal Published version, 1.12 MBLicence: CC BY

https://www.jmlr.org/papers/v27/23-0737.html

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{c6e278de8d8841ffb3166459bf271c77,

title = "Efficient frequent directions algorithms for approximate decomposition of matrices and higher-order tensors",

abstract = "In the framework of the FD (frequent directions) algorithm, we first develop two efficient algorithms for low-rank matrix approximations under the embedding matrices composed of the product of any SpEmb (sparse embedding) matrix and any standard Gaussian matrix, or any SpEmb matrix and any SRHT (subsampled randomized Hadamard transform) matrix. The theoretical results are also achieved based on the bounds of singular values of standard Gaussian matrices and the theoretical results for SpEmb and SRHT matrices. With a given Tucker-rank, we then obtain several efficient FD-based randomized variants of T-HOSVD (the truncated high-order singular value decomposition) and ST-HOSVD (sequentially T-HOSVD), which are two common algorithms for computing the approximate Tucker decomposition of any tensor with a given Tucker-rank. We also consider efficient FD-based randomized algorithms for computing the approximate TT (tensor-train) decomposition of any tensor with a given TT-rank. Finally, we illustrate the efficiency and accuracy of these algorithms using synthetic and real-world matrix (and tensor) data. {\textcopyright}2026 Maolin Che, Yimin Wei and Hong Yan.",

keywords = "approximate TT decomposition, approximate Tucker decomposition, classification, frequent directions, Low-rank approximation, random projection, randomized algorithms, sparse embedding matrices, ST-HOSVD, standard Gaussian matrices, subsampled randomized Hadamard transform, T-HOSVD, TT-SVD",

author = "Maolin Che and Yimin Wei and Hong Yan",

year = "2026",

month = feb,

language = "English",

volume = "27",

pages = "1--56",

journal = "Journal of Machine Learning Research",

issn = "1532-4435",

publisher = "Microtome Publishing",

number = "3",

}

TY - JOUR

T1 - Efficient frequent directions algorithms for approximate decomposition of matrices and higher-order tensors

AU - Che, Maolin

AU - Wei, Yimin

AU - Yan, Hong

PY - 2026/2

Y1 - 2026/2

N2 - In the framework of the FD (frequent directions) algorithm, we first develop two efficient algorithms for low-rank matrix approximations under the embedding matrices composed of the product of any SpEmb (sparse embedding) matrix and any standard Gaussian matrix, or any SpEmb matrix and any SRHT (subsampled randomized Hadamard transform) matrix. The theoretical results are also achieved based on the bounds of singular values of standard Gaussian matrices and the theoretical results for SpEmb and SRHT matrices. With a given Tucker-rank, we then obtain several efficient FD-based randomized variants of T-HOSVD (the truncated high-order singular value decomposition) and ST-HOSVD (sequentially T-HOSVD), which are two common algorithms for computing the approximate Tucker decomposition of any tensor with a given Tucker-rank. We also consider efficient FD-based randomized algorithms for computing the approximate TT (tensor-train) decomposition of any tensor with a given TT-rank. Finally, we illustrate the efficiency and accuracy of these algorithms using synthetic and real-world matrix (and tensor) data. ©2026 Maolin Che, Yimin Wei and Hong Yan.

AB - In the framework of the FD (frequent directions) algorithm, we first develop two efficient algorithms for low-rank matrix approximations under the embedding matrices composed of the product of any SpEmb (sparse embedding) matrix and any standard Gaussian matrix, or any SpEmb matrix and any SRHT (subsampled randomized Hadamard transform) matrix. The theoretical results are also achieved based on the bounds of singular values of standard Gaussian matrices and the theoretical results for SpEmb and SRHT matrices. With a given Tucker-rank, we then obtain several efficient FD-based randomized variants of T-HOSVD (the truncated high-order singular value decomposition) and ST-HOSVD (sequentially T-HOSVD), which are two common algorithms for computing the approximate Tucker decomposition of any tensor with a given Tucker-rank. We also consider efficient FD-based randomized algorithms for computing the approximate TT (tensor-train) decomposition of any tensor with a given TT-rank. Finally, we illustrate the efficiency and accuracy of these algorithms using synthetic and real-world matrix (and tensor) data. ©2026 Maolin Che, Yimin Wei and Hong Yan.

KW - approximate TT decomposition

KW - approximate Tucker decomposition

KW - classification

KW - frequent directions

KW - Low-rank approximation

KW - random projection

KW - randomized algorithms

KW - sparse embedding matrices

KW - ST-HOSVD

KW - standard Gaussian matrices

KW - subsampled randomized Hadamard transform

KW - T-HOSVD

KW - TT-SVD

UR - http://www.scopus.com/inward/record.url?scp=105031780812&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-105031780812&origin=recordpage

M3 - RGC 21 - Publication in refereed journal

SN - 1532-4435

VL - 27

SP - 1

EP - 56

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

IS - 3

ER -

Efficient frequent directions algorithms for approximate decomposition of matrices and higher-order tensors

Abstract

Funding

Research Keywords

Publisher's Copyright Statement

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this