Most Tensor Problems Are NP-Hard

From MaRDI portal
Revision as of 01:23, 9 February 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Publication:5395740

DOI10.1145/2512329zbMath1281.68126DBLPjournals/jacm/HillarL13arXiv0911.1393OpenAlexW2079705627WikidataQ60307003 ScholiaQ60307003MaRDI QIDQ5395740

Lek-Heng Lim, Christopher J. Hillar

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

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




Related Items (only showing first 100 items - show all)

Robust Eigenvectors of Symmetric TensorsTensors in computationsSeparability of Hermitian tensors and PSD decompositionsOrthogonal decomposition of tensor trainsUnnamed ItemThe Geometry of Rank-One Tensor CompletionHalf-quadratic alternating direction method of multipliers for robust orthogonal tensor approximationIterative hard thresholding for low CP-rank tensor modelsNonlinear Perron--Frobenius Theorems for Nonnegative TensorsLow-rank tensor methods for partial differential equationsSome new \(Z\)-eigenvalue localization sets for even-order tensors and their application in the geometric measure of entanglementCommunity detection in the sparse hypergraph stochastic block modelAlternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP DecompositionFully-connected tensor network decomposition for robust tensor completion problemPartially symmetric tensor structure preserving rank-\(R\) approximation via BFGS algorithmLow tubal rank tensor completion based on singular value factorsApproximate real symmetric tensor rankOn the stability of discrete-time homogeneous polynomial dynamical systemsTensor completion via multi-directional partial tensor nuclear norm with total variation regularizationAdaptive tensor networks decomposition for high-order tensor recovery and compressionSome properties on eccentricity matrices of uniform hypertreesSome bounds on spectral radius of signless Laplacian matrix of k-graphsThe low-rank approximation of fourth-order partial-symmetric and conjugate partial-symmetric tensorA complex-valued gradient flow for the entangled bipartite low rank approximationSpectral theory of weighted hypergraphs via tensorsOn Best Low Rank Approximation of Positive Definite TensorsA Learnable Group-Tube Transform Induced Tensor Nuclear Norm and Its Application for Tensor CompletionTR-STF: a fast and accurate tensor ring decomposition algorithm via defined scaled tri-factorizationFeasible Newton methods for symmetric tensor Z-eigenvalue problemsA Corrected Tensor Nuclear Norm Minimization Method for Noisy Low-Rank Tensor CompletionApproximating Tensor Norms via Sphere Covering: Bridging the Gap between Primal and DualTensor decompositions on simplicial complexes with invarianceMore on Tensors with Different Rank and Symmetric RankApproximating Higher-Order Derivative Tensors Using Secant UpdatesFactor Models for High-Dimensional Tensor Time SeriesSymmetric Tensor Nuclear NormsHankel Tensor Decompositions and RanksAnalytical expressions of copositivity for fourth-order symmetric tensorsOn the irregularity of uniform hypergraphsLow-Rank Tensor Recovery using Sequentially Optimal Modal Projections in Iterative Hard Thresholding (SeMPIHT)The Sup-norm Perturbation of HOSVD and Low Rank Tensor DenoisingComputing Tensor $Z$-Eigenvectors with Dynamical SystemsOn isolation of simple multiple zeros and clusters of zeros of polynomial systemsOptimal Sparse Singular Value Decomposition for High-Dimensional High-Order DataApproximating the existential theory of the realsApproximating the existential theory of the reals${}_{\delta}^{\gamma}\!\mathbf{\Phi}$-type inclusion set for eigenvalues of a tensorRigid continuation paths I. Quasilinear average complexity for solving polynomial systemsA TT-Based Hierarchical Framework for Decomposing High-Order TensorsA Unifying Perron--Frobenius Theorem for Nonnegative Tensors via Multihomogeneous MapsPositive contraction mappings for classical and quantum Schrödinger systemsHardness and Approximation Results for Lp-Ball Constrained Homogeneous Polynomial Optimization ProblemsNonlocal robust tensor recovery with nonconvex regularization *Tensor Spaces and Hierarchical Tensor RepresentationsGuarantees for Existence of a Best Canonical Polyadic Approximation of a Noisy Low-Rank TensorRobust Tensor Completion: Equivalent Surrogates, Error Bounds, and AlgorithmsA generalization of inverse power method for computing eigenpairs of symmetric tensorsA Semidefinite Relaxation Method for Partially Symmetric Tensor DecompositionTensor Regression Using Low-Rank and Sparse Tucker DecompositionsErgodicity Coefficients for Higher-Order Stochastic ProcessesFurther results on sum-of-squares tensorsA public key cryptosystem based on data complexity under quantum environmentAn adaptive gradient method for computing generalized tensor eigenpairsOn $\ell_p$-Support Vector Machines and Multidimensional KernelsThe Optimization Landscape for Fitting a Rank-2 Tensor with a Rank-1 TensorNewton Correction Methods for Computing Real Eigenpairs of Symmetric TensorsSuccessive Rank-One Approximations for Nearly Orthogonally Decomposable Symmetric TensorsAn Adaptive Correction Approach for Tensor CompletionHow to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCATensor Completion in Hierarchical Tensor RepresentationsA Counterexample to Comon's ConjectureRank-1 Tensor Properties with Applications to a Class of Tensor Optimization ProblemsQuantum machine learning: a classical perspectiveQuantum algorithm for multivariate polynomial interpolationA General Theory of Singular Values with Applications to Signal DenoisingA note on the gap between rank and border rankHigh-dimensional change-point estimation: combining filtering with convex optimizationGenerating polynomials and symmetric tensor decompositionsUnnamed ItemComputing extreme eigenvalues of large scale Hankel tensorsOn probabilistic algorithm for solving almost all instances of the set partition problemLow rank tensor recovery via iterative hard thresholdingStatistically optimal and computationally efficient low rank tensor completion from noisy entriesNonconvex Low-Rank Tensor Completion from Noisy DataGeneralized notions of sparsity and restricted isometry property. II: ApplicationsStatistical thresholds for tensor PCAWhen does OMP achieve exact recovery with continuous dictionaries?Robust low transformed multi-rank tensor methods for image alignmentAn approximation method of CP rank for third-order tensor completionOptimization on the Euclidean Unit SphereRecognition of absolutely irreducible matrix groups that are tensor decomposable or inducedThe symmetric rank and decomposition of \(m\)-order \(n\)-dimensional \((n = 2,3,4)\) symmetric tensors over the binary fieldUnnamed ItemKronecker-structured covariance models for multiway dataThe average number of critical rank-one approximations to a tensorGeneralized eigenvalue for even order tensors via Einstein product and its applications in multilinear control systemsMaximization of homogeneous polynomials over the simplex and the sphere: structure, stability, and generic behaviorRapid solution of problems by quantum computationRank properties and computational methods for orthogonal tensor decompositionsRandomized algorithms in numerical linear algebra




This page was built for publication: Most Tensor Problems Are NP-Hard