Positive Moments Forever: Undecidable and Decidable Cases

• URL: http://arxiv.org/abs/2404.15053v1
• Date: Tue, 23 Apr 2024 13:53:37 GMT
• Title: Positive Moments Forever: Undecidable and Decidable Cases
• Authors: Gemma De les Coves, Joshua Graf, Andreas Klingler, Tim Netzer,
• Abstract summary: We show that the positivity problem for simple unitary linear recurrence sequences is decidable, and is undecidable for linear recurrence sequences over the ring of commutatives. As a byproduct, we prove a free version of Polya's theorem.
• Score: 1.3124513975412255
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Is there an algorithm to determine attributes such as positivity or non-zeroness of linear recurrence sequences? This long-standing question is known as Skolem's problem. In this paper, we study the complexity of an equivalent problem, namely the (generalized) moment membership problem for matrices. We show that this problem is decidable for orthogonal, unitary and real eigenvalue matrices, and undecidable for matrices over certain commutative and non-commutative polynomial rings. Our results imply that the positivity problem for simple unitary linear recurrence sequences is decidable, and is undecidable for linear recurrence sequences over the ring of commutative polynomials. As a byproduct, we prove a free version of Polya's theorem.

Related papers

• Mutually-orthogonal unitary and orthogonal matrices [6.9607365816307]
  We show that the minimum and maximum numbers of an unextendible maximally entangled bases within a real two-qutrit system are three and four, respectively. As an application in quantum information theory, we show that the minimum and maximum numbers of an unextendible maximally entangled bases within a real two-qutrit system are three and four, respectively.
  arXiv  Detail & Related papers  (2023-09-20T08:20:57Z)
• Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond [8.604882842499212]
  We study the problem of finding elements in the intersection of an arbitrary conic variety in $mathbbFn$ with a given linear subspace. This problem captures a rich family of algorithmic problems under different choices of the variety. We develop an algorithm that solves this problem efficiently for "typical" subspaces.
  arXiv  Detail & Related papers  (2022-12-07T18:45:33Z)
• Identifiability in Exact Two-Layer Sparse Matrix Factorization [0.0]
  Sparse matrix factorization is the problem of approximating a matrix Z by a product of L sparse factors X(L) X(L--1). This paper focuses on identifiability issues that appear in this problem, in view of better understanding under which sparsity constraints the problem is well-posed.
  arXiv  Detail & Related papers  (2021-10-04T07:56:37Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Exact recursive calculation of circulant permanents: A band of different diagonals inside a uniform matrix [0.0]
  The proposed system of linear recurrence equations with variable coefficients provides a powerful tool for the analysis of the circulants. Its solution would be tremendously important for a unified analysis of a wide range of the nature's #P-hard problems.
  arXiv  Detail & Related papers  (2021-09-03T21:56:14Z)
• Feature Cross Search via Submodular Optimization [58.15569071608769]
  We study feature cross search as a fundamental primitive in feature engineering. We show that there exists a simple greedy $(1-1/e)$-approximation algorithm for this problem.
  arXiv  Detail & Related papers  (2021-07-05T16:58:31Z)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  We study the asymmetric low-rank factorization problem: [mathbfU in mathbbRm min d, mathbfU$ and mathV$.
  arXiv  Detail & Related papers  (2021-06-27T17:25:24Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Can Single-Shuffle SGD be Better than Reshuffling SGD and GD? [77.82009268160053]
  We conjecture that the means of matrix products corresponding to with- and without-replacement variants of SGD satisfy a series of spectral norm inequalities. We present theorems that support our conjecture by proving several special cases.
  arXiv  Detail & Related papers  (2021-03-12T04:34:45Z)
• Simultaneous Block Diagonalization of Matrices of Finite Order [0.0]
  It is well known that a set of non-defect matrices can be simultaneously diagonalized if and only if the matrices commute. Here we give an efficient algorithm to explicitly compute a transfer matrix which realizes the simultaneous block diagonalization. Our main motivation lies in particle physics, where the resulting transfer matrix must be known explicitly in order to unequivocally determine the action of outer automorphisms.
  arXiv  Detail & Related papers  (2020-12-28T19:00:06Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  We introduce an eigendecomposition-free approach to training a deep network. We show that our approach is much more robust than explicit differentiation of the eigendecomposition. Our method has better convergence properties and yields state-of-the-art results.
  arXiv  Detail & Related papers  (2020-04-15T04:29:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.