Exact clustering in tensor block model: Statistical optimality and computational limit

Rungang Han, Yuetian Luo, Miaoyan Wang and Anru R. Zhang

Journal of the Royal Statistical Society Series B, 2022, vol. 84, issue 5, 1666-1698

Abstract: High‐order clustering aims to identify heterogeneous substructures in multiway datasets that arise commonly in neuroimaging, genomics, social network studies, etc. The non‐convex and discontinuous nature of this problem pose significant challenges in both statistics and computation. In this paper, we propose a tensor block model and the computationally efficient methods, high‐order Lloyd algorithm (HLloyd), and high‐order spectral clustering (HSC), for high‐order clustering. The convergence guarantees and statistical optimality are established for the proposed procedure under a mild sub‐Gaussian noise assumption. Under the Gaussian tensor block model, we completely characterise the statistical‐computational trade‐off for achieving high‐order exact clustering based on three different signal‐to‐noise ratio regimes. The analysis relies on new techniques of high‐order spectral perturbation analysis and a ‘singular‐value‐gap‐free’ error bound in tensor estimation, which are substantially different from the matrix spectral analyses in the literature. Finally, we show the merits of the proposed procedures via extensive experiments on both synthetic and real datasets.

Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1111/rssb.12547

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:jorssb:v:84:y:2022:i:5:p:1666-1698

Ordering information: This journal article can be ordered from
http://ordering.onli ... 1111/(ISSN)1467-9868

Access Statistics for this article

Journal of the Royal Statistical Society Series B is currently edited by P. Fryzlewicz and I. Van Keilegom

More articles in Journal of the Royal Statistical Society Series B from Royal Statistical Society Contact information at EDIRC.
Bibliographic data for series maintained by Wiley Content Delivery ().