Efficient Algorithms for Verifying Kruskal Rank in Sparse Linear Regression and Related Applications
We present novel algorithmic techniques to efficiently verify the Kruskal rank of matrices that arise in sparse linear regression, tensor decomposition, and latent variable models. Our unified framework combines randomized hashing techniques with dynamic programming strategies, and is applicable in various settings, including binary fields, general finite fields, and integer matrices. In particular, our algorithms achieve a runtime of $\mathcal{O}\left(dk \cdot \left(nM\right)^{\lceil k / 2 \rceil}\right)$ while ensuring high-probability correctness. Our contributions include: A unified framework for verifying Kruskal rank across different algebraic settings; Rigorous runtime and high-probability guarantees that nearly match known lower bounds; Practical implications for identifiability in tensor decompositions and deep learning, particularly for the estimation of noise transition matrices.
Code (0)
등록된 구현이 없습니다.
Tasks
Tensor DecompositionSimilar Papers 제목 키워드 기반
Tensor-Dictionary Learning with Deep Kruskal-Factor Analysis
A multi-way factor analysis model is introduced for tensor-variate data of any order. Each data item is represented as a (sparse) sum of Kruskal decompositions, a Kruskal-factor analysis (KFA). KFA is nonparametric and c…
DenoisingDictionary LearningGeneral Classificationimage-classification+1Array-Informed Waveform Design for Active Sensing: Diversity, Redundancy, and Identifiability
This paper investigates the combined role of transmit waveforms and (sparse) sensor array geometries in active sensing multiple-input multiple-output (MIMO) systems. Specifically, we consider the fundamental identifiabil…
DiversityTensor Convolutional Sparse Coding with Low-Rank activations, an application to EEG analysis
Recently, there has been growing interest in the analysis of spectrograms of ElectroEncephaloGram (EEG), particularly to study the neural correlates of (un)-consciousness during General Anesthesia (GA). Indeed, it has be…
EEGElectroencephalogram (EEG)Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability
We give a robust version of the celebrated result of Kruskal on the uniqueness of tensor decompositions: we prove that given a tensor whose decomposition satisfies a robust form of Kruskal's rank condition, it is possibl…
Topic ModelsMultivariate Convolutional Sparse Coding with Low Rank Tensor
This paper introduces a new multivariate convolutional sparse coding based on tensor algebra with a general model enforcing both element-wise sparsity and low-rankness of the activations tensors. By using the CP decompos…
regressiontensor algebra