Open problems

1131 registered problems.

OP-00201 Partially resolved

Two-vertex certification of nonsingular sign regularity

NA · interval matrices · OpenProblemsInNLA · sign regular matrices · totally nonnegative matrices

OP-00202 Open

Polynomial-time minimum-volume decision under sufficient scattering

NA · minimum-volume factorizations · nonnegative matrix factorizations · OpenProblemsInNLA · promise problems

OP-00203 Partially resolved

Exact nonnegative rank of regular polygon slack matrices

NA · extended formulations · nonnegative rank · OpenProblemsInNLA · regular polygons

OP-00204 Partially resolved

Additivity for Cartesian-product slack matrices

NA · Cartesian products · extended formulations · nonnegative rank · OpenProblemsInNLA

OP-00205 Partially resolved

Exact positive semidefinite rank of subset-intersection matrices

NA · Johnson schemes · OpenProblemsInNLA · positive semidefinite factorizations · positive semidefinite rank

OP-00206 Solution claimed

Optimal dimension for a rerandomized Hadamard embedding

NA · OpenProblemsInNLA · randomized Hadamard transforms · sketching · subspace embeddings

OP-00207 Solution claimed

Improve the worst-case approximation factor for prescribed tensor-train ranks

NA · approximation algorithms · low-rank approximations · OpenProblemsInNLA · tensor-train decompositions

OP-00208 Solution claimed

Finite mean angular condition number for identifiable tensor decomposition

NA · condition numbers · OpenProblemsInNLA · random tensors · tensor decompositions

OP-00209 Solution claimed

Sharp sparsity threshold for injectivity of a random sparse rectangular matrix

PR · OpenProblemsInNLA · smallest singular values · sparse random matrices · subspace injections

OP-00210 Lean verified

Equality of ranks for generic odd-order Hankel tensors

AG · border ranks · Hankel tensors · OpenProblemsInNLA · tensor ranks

OP-00211 Lean verified

Comon's exact-rank conjecture for Hankel tensors

AG · Hankel tensors · OpenProblemsInNLA · symmetric tensors · tensor ranks

OP-00212 Solution claimed

Frobenius inner products minimize the algebraic complexity of rank-one approximation

AG · Euclidean distance degrees · OpenProblemsInNLA · rank-one approximations · Segre–Veronese varieties

OP-00213 Solution claimed

Rayleigh–Ritz discriminant degrees for rank-one matrices

AG · discriminants · OpenProblemsInNLA · Rayleigh quotients · Segre varieties

OP-00214 Solution claimed

A Seginer theorem for arbitrary independent identically distributed tensor entries

PR · injective norms · OpenProblemsInNLA · random tensors

OP-00215 Solution claimed

Degrees of the two Rayleigh–Ritz discriminant parts for rational normal curves

AG · discriminants · OpenProblemsInNLA · rational normal curves · Rayleigh quotients

OP-00216 Solution claimed

Border-rank deficiency forcing strict submultiplicativity at the tensor square

AG · border ranks · OpenProblemsInNLA · secant varieties · tensor products

OP-00217 Solution claimed

Forsythe's conjecture beyond restart length two

NA · conjugate gradient methods · Krylov subspace methods · OpenProblemsInNLA

OP-00218 Solution claimed

The square-root upper bound for Gaussian partial-pivoting growth

NA · Gaussian elimination · growth factors · OpenProblemsInNLA · random matrices

OP-00219 Solution claimed

A cubic-time Schur algorithm using logarithmic precision

NA · floating-point arithmetic · OpenProblemsInNLA · randomized algorithms · Schur decompositions

OP-00220 Solution claimed

Conditioning of a random Krylov compression of a cyclic shift

NA · circulant matrices · eigenvector condition numbers · Krylov subspaces · OpenProblemsInNLA

OP-00221 Solution claimed

Near-quadratic solution cost at a prescribed backward error

NA · backward errors · linear systems · OpenProblemsInNLA · randomized algorithms

OP-00222 Solution claimed

Sharp growth for unequal lower and upper bandwidths

NA · banded matrices · Gaussian elimination · growth factors · OpenProblemsInNLA

OP-00223 Solution claimed

Sharp growth for cyclic tridiagonal matrices

NA · Gaussian elimination · growth factors · OpenProblemsInNLA · tridiagonal matrices

OP-00224 Solution claimed

Exact small-order growth factors for rook pivoting

NA · Gaussian elimination · growth factors · OpenProblemsInNLA · rook pivoting

OP-00225 Solution claimed

Sharp row-deletion singular-value limit for spherical random matrices

NA · Kaczmarz methods · OpenProblemsInNLA · random matrices · smallest singular values

OP-00226 Solution claimed

Optimal uniform row-deletion singular-value constant

NA · corrupted linear systems · Kaczmarz methods · OpenProblemsInNLA · smallest singular values

OP-00227 Solution claimed

Sharp stability bounds for perturbed Fourier interpolation

NA · Lebesgue constants · nonuniform Fourier matrices · OpenProblemsInNLA · trigonometric interpolation

OP-00228 Solution claimed

Find a near-largest nonnormal eigenvalue using few matrix-vector products

NA · eigenvalue algorithms · nonnormal matrices · OpenProblemsInNLA · query complexity

OP-00229 Solution claimed

Spectral-gap-independent constants for randomized block polynomial interpolation

NA · block Lanczos methods · matrix polynomials · OpenProblemsInNLA · random matrices

OP-00230 Solution claimed

Multiplication overhead of cubic sign compositions

NA · matrix sign function · OpenProblemsInNLA · polynomial approximation · polynomial compositions

OP-00231 Solution claimed

A uniform disk bound for wave-kernel Padé approximants

NA · backward error analysis · matrix functions · OpenProblemsInNLA · Padé approximants

OP-00232 Solution claimed

NP-hardness of unrestricted static output-feedback stabilization

OC · Hurwitz matrices · NP-hardness · OpenProblemsInNLA · static output feedback

OP-00233 Solution claimed

Uniqueness of positive definite solutions of two-letter word equations in order two

NA · nonlinear matrix equations · OpenProblemsInNLA · positive definite matrices · word equations

OP-00234 Solution claimed

Complete Crouzeix conjecture

FA · matrix polynomials · numerical ranges · OpenProblemsInNLA · spectral sets

OP-00235 Solution claimed

A dimension-independent polynomial norm bound from super-identical pseudospectra

NA · matrix polynomials · OpenProblemsInNLA · pseudospectra · singular values

OP-00236 Solution claimed

Preservation of real H-matrix structure by Newton square-root iterates

NA · H-matrices · matrix square roots · Newton iterations · OpenProblemsInNLA

OP-00237 Solution claimed

Clustered singular-value gaps in randomized block Krylov approximation

NA · Krylov subspace methods · low-rank approximations · OpenProblemsInNLA · singular value gaps

OP-00238 Solution claimed

Sharp joint rank and accuracy dependence for strong ℓₚ subspace coresets

NA · coresets · low-rank approximations · OpenProblemsInNLA · subspace approximation

OP-00239 Lean verified

Sensitivity-dependent row sampling for ℓₚ embeddings when p exceeds two

NA · OpenProblemsInNLA · row sampling · sensitivity sampling · subspace embeddings

OP-00240 Solution claimed

Concave-function transfer of spectral low-rank error

NA · low-rank approximations · matrix functions · Nyström approximations · OpenProblemsInNLA

OP-00241 Solution claimed

Concave-function transfer of Frobenius low-rank error

NA · low-rank approximations · matrix functions · Nyström approximations · OpenProblemsInNLA

OP-00242 Solution claimed

Constant-loss nuclear-error transfer without matrix ordering

NA · low-rank approximations · matrix functions · OpenProblemsInNLA · operator monotone functions

OP-00243 Solution claimed

Relative-error threshold for extremal Gaussian trace bounds

NA · Gamma distributions · OpenProblemsInNLA · tail bounds · trace estimation

OP-00244 Solution claimed

Absolute-error threshold for extremal Gaussian trace bounds

NA · Gamma distributions · OpenProblemsInNLA · tail bounds · trace estimation

OP-00245 Solution claimed

Critical-point count for corank-one approximation with a fixed zero

AG · determinantal varieties · Euclidean distance degrees · low-rank approximations · OpenProblemsInNLA

OP-00246 Solution claimed

Pure relative error for approximation by a linear matrix family

NA · matrix-vector queries · OpenProblemsInNLA · query complexity · structured matrices

OP-00247 Solution claimed

Nonadaptive queries for finite-family matrix approximation

NA · matrix-vector queries · nonadaptive algorithms · OpenProblemsInNLA · query complexity

OP-00248 Solution claimed

A sum-of-squares representation for the Toeplitz commutator form

FA · Böttcher–Wenzel inequality · OpenProblemsInNLA · sums of squares · Toeplitz matrices

OP-00249 Solution claimed

Schatten norm complement involving Lin's positive definite quantity

FA · matrix geometric means · norm inequalities · OpenProblemsInNLA · Schatten norms

OP-00250 Solution claimed

Ghabries's determinant comparison for arbitrary nonnegative base powers

FA · determinantal inequalities · OpenProblemsInNLA · positive definite matrices