Symmetric Tensor Completion from Multilinear Entries and Learning Product Mixtures over the Hypercube
We give an algorithm for completing an order-$m$ symmetric low-rank tensor from its multilinear entries in time roughly proportional to the number of tensor entries. We apply our tensor completion algorithm to the problem of learning mixtures of product distributions over the hypercube, obtaining new algorithmic results. If the centers of the product distribution are linearly independent, then we recover distributions with as many as $\Omega(n)$ centers in polynomial time and sample complexity. In the general case, we recover distributions with as many as $\tilde\Omega(n)$ centers in quasi-polynomial time, answering an open problem of Feldman et al. (SIAM J. Comp.) for the special case of distributions with incoherent bias vectors. Our main algorithmic tool is the iterated application of a low-rank matrix completion algorithm for matrices with adversarially missing entries.
Code (0)
등록된 구현이 없습니다.
Tasks
Low-Rank Matrix CompletionMatrix CompletionSimilar Papers 제목 키워드 기반
Novel methods for multilinear data completion and de-noising based on tensor-SVD
In this paper we propose novel methods for completion (from limited samples) and de-noising of multilinear (tensor) data and as an application consider 3-D and 4- D (color) video data completion and de-noising. We exploi…
Novel Factorization Strategies for Higher Order Tensors: Implications for Compression and Recovery of Multi-linear Data
In this paper we propose novel methods for compression and recovery of multilinear data under limited sampling. We exploit the recently proposed tensor- Singular Value Decomposition (t-SVD)[1], which is a group theoretic…
Data CompressionTensor DecompositionExact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
In this paper we show that simple semidefinite programs inspired by degree $4$ SOS can exactly solve the tensor nuclear norm, tensor decomposition, and tensor completion problems on tensors with random asymmetric compone…
Tensor DecompositionBayesian Sparse Tucker Models for Dimension Reduction and Tensor Completion
Tucker decomposition is the cornerstone of modern machine learning on tensorial data analysis, which have attracted considerable attention for multiway feature extraction, compressive sensing, and tensor completion. The …
Compressive SensingDimensionality ReductionTensor DecompositionBayesian CP Factorization of Incomplete Tensors with Automatic Rank Determination
CANDECOMP/PARAFAC (CP) tensor factorization of incomplete data is a powerful technique for tensor completion through explicitly capturing the multilinear latent factors. The existing CP algorithms require the tensor rank…
Bayesian InferenceImage GenerationImage Inpainting