Deterministic tensor completion with hypergraph expanders

DOI10.1137/20M1379745MaRDI QIDQ5162629zbMATH OpenOpenAlexFDO

Authors Kameron Decker Harris, Yizhe Zhu

Publication date 3 November 2021

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.10692

zbMATH Keywords

linear algebrahypergraphtensor completionexpander

Mathematics Subject Classification ID

Applications of graph theory (05C90) Multilinear algebra, tensor calculus (15A69) Hypergraphs (05C65) Expander graphs (05C48)

Abstract: We provide a novel analysis of low-rank tensor completion based on hypergraph expanders. As a proxy for rank, we minimize the max-quasinorm of the tensor, which generalizes the max-norm for matrices. Our analysis is deterministic and shows that the number of samples required to approximately recover an order-$t$ tensor with at most $n$ entries per dimension is linear in $n$, under the assumption that the rank and order of the tensor are $O(1)$. As steps in our proof, we find a new expander mixing lemma for a $t$-partite, $t$-uniform regular hypergraph model, and prove several new properties about tensor max-quasinorm. To the best of our knowledge, this is the first deterministic analysis of tensor completion. We develop a practical algorithm that solves a relaxed version of the max-quasinorm minimization problem, and we demonstrate its efficacy with numerical experiments.

Recommendations

• On tensor completion via nuclear norm minimization
• Spectral algorithms for tensor completion
• On polynomial time methods for exact low-rank tensor completion
• Fundamental conditions for low-CP-rank tensor completion
• Cross: efficient low-rank tensor completion

Cites work

• scientific article; zbMATH DE number 194266 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A Deterministic Theory of Low Rank Matrix Completion
• A combinatorial construction of almost-Ramanujan graphs using the zig-zag product
• A simpler approach to matrix completion
• Complexity measures of sign matrices
• Cross: efficient low-rank tensor completion
• Derandomized graph products
• Deterministic Completion of Rectangular Matrices Using Asymmetric Ramanujan Graphs: Exact and Stable Recovery
• Deterministic algorithms for matrix completion
• Eigenvalues and expanders
• Eigenvalues and expansion of regular graphs
• Eigenvalues and linear quasirandom hypergraphs
• Expander graphs and their applications
• Explicit near-Ramanujan graphs of every degree
• Factorization norms and hereditary discrepancy
• HIGH DIMENSIONAL EXPANDERS
• Interlacing eigenvalues and graphs
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Inverse expander mixing for hypergraphs
• Large incidence-free sets in geometries
• Learning Theory
• Lifts, discrepancy and nearly optimal spectral gap
• Matrix Completion From a Few Entries
• Matrix completion via max-norm constrained optimization
• Mixing in high-dimensional expanders
• Most tensor problems are NP-hard
• Near-optimal sample complexity for convex tensor completion
• Noisy low-rank matrix completion with general sampling distribution
• Nuclear norm of higher-order tensors
• On codes from hypergraphs.
• On polynomial time methods for exact low-rank tensor completion
• On tensor completion via nuclear norm minimization
• On the second eigenvalue of hypergraphs
• Sparse random tensors: concentration, regularization and applications
• Spectra of random regular hypergraphs
• Spectral algorithms for tensor completion
• Tensor Decompositions and Applications
• Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
• The dimension of Euclidean subspaces of quasi-normed spaces
• Weighted Matrix Completion From Non-Random, Non-Uniform Sampling Patterns

Cited in

(6)

• Entrywise tensor-train approximation of large tensors via random embeddings
• Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model
• When big data actually are low-rank, or entrywise approximation of certain function-generated matrices
• Sparse random hypergraphs: non-backtracking spectra and community detection
• Fundamental conditions for low-CP-rank tensor completion
• Characterization of sampling patterns for low-tt-rank tensor retrieval

Describes a project that uses

Uses Software

• Cross

This page was built for publication: Deterministic tensor completion with hypergraph expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5162629)