Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2302.02415 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917350468485120 |
|---|---|
| author | Song, Dogyoon Hero, Alfred O. |
| author_facet | Song, Dogyoon Hero, Alfred O. |
| contents | Multiway data analysis aims to uncover patterns in data structured as multi-indexed arrays, with multiway covariance playing a crucial role in many applications. However, the high dimensionality of multiway covariance presents significant computational challenges. To overcome these challenges, factorized covariance models have been proposed that rely on a separability assumption: the multiway covariance can be accurately expressed as a sum of Kronecker products of mode-wise covariances. This paper addresses the representability, certification, and approximation of such separable models, leaving statistical estimation or finite-sample properties aside. We reduce the question of whether a given covariance can be decomposed into a separable multiway form to an equivalent question about the separability of quantum states. Leveraging results from quantum information theory, we show that generic multiway covariances are typically \emph{not} separable and that determining the best separable approximation is NP-hard. These findings suggest that factorized covariance models can be overly restrictive and difficult to fit without additional structural assumptions. Nevertheless, our numerical experiments indicate that standard iterative algorithms, namely Frank-Wolfe and gradient descent, often converge close to the best separable approximation. As NP-hardness concerns worst-case computational complexity, Kronecker-separable approximations to multiway covariance could still be tractable to apply for analyzing many real-world datasets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_02415 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On Separability of Covariance in Multiway Data Analysis Song, Dogyoon Hero, Alfred O. Statistics Theory Methodology 15A69, 15B48, 62H99 Multiway data analysis aims to uncover patterns in data structured as multi-indexed arrays, with multiway covariance playing a crucial role in many applications. However, the high dimensionality of multiway covariance presents significant computational challenges. To overcome these challenges, factorized covariance models have been proposed that rely on a separability assumption: the multiway covariance can be accurately expressed as a sum of Kronecker products of mode-wise covariances. This paper addresses the representability, certification, and approximation of such separable models, leaving statistical estimation or finite-sample properties aside. We reduce the question of whether a given covariance can be decomposed into a separable multiway form to an equivalent question about the separability of quantum states. Leveraging results from quantum information theory, we show that generic multiway covariances are typically \emph{not} separable and that determining the best separable approximation is NP-hard. These findings suggest that factorized covariance models can be overly restrictive and difficult to fit without additional structural assumptions. Nevertheless, our numerical experiments indicate that standard iterative algorithms, namely Frank-Wolfe and gradient descent, often converge close to the best separable approximation. As NP-hardness concerns worst-case computational complexity, Kronecker-separable approximations to multiway covariance could still be tractable to apply for analyzing many real-world datasets. |
| title | On Separability of Covariance in Multiway Data Analysis |
| topic | Statistics Theory Methodology 15A69, 15B48, 62H99 |
| url | https://arxiv.org/abs/2302.02415 |