Open problems

1131 registered problems.

OP-00151 Partially resolved

Construct a separating diagonal perturbation in nearly linear time

NA · deterministic algorithms · eigenvalue gaps · OpenProblemsInNLA · tridiagonal matrices

OP-00152 Open

The sharp generic threshold for spectral-subspace rotation

SP · OpenProblemsInNLA · perturbation bounds · self-adjoint operators · spectral subspaces

OP-00153 Open

The sharp off-diagonal threshold for spectral-subspace rotation

SP · off-diagonal perturbations · OpenProblemsInNLA · perturbation bounds · spectral subspaces

OP-00154 Partially resolved

The Euclidean distance degree of the real symplectic group

NA · Euclidean distance degree · matrix nearness problems · OpenProblemsInNLA · symplectic groups

OP-00155 Partially resolved

The sharp spectral-matching constant for normal matrices

NA · normal matrices · OpenProblemsInNLA · perturbation bounds · spectral variation

OP-00156 Partially resolved

Rank-two maximizers of spectral spread on an entry interval

NA · Bohemian matrices · matrix spread · OpenProblemsInNLA

OP-00157 Partially resolved

Unitary-orbit distance under finite block repetition

NA · matrix nearness problems · normal matrices · OpenProblemsInNLA · unitary orbits

OP-00158 Partially resolved

The graph complement conjecture for minimum symmetric rank

CO · graph complements · inverse eigenvalue problems · minimum rank · OpenProblemsInNLA

OP-00159 Solution claimed

Widom's canonical distribution conjecture for Toeplitz eigenvalues

SP · eigenvalue distributions · OpenProblemsInNLA · Toeplitz matrices

OP-00160 Open

Optimal sign approximation with a multiplication budget

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

OP-00161 Open

Finiteness for nonnegative rational matrix families

DS · finiteness property · joint spectral radius · nonnegative matrices · OpenProblemsInNLA

OP-00162 Open

Decidability of strict stability for rational matrix families

DS · decidability · joint spectral radius · OpenProblemsInNLA · switched linear systems

OP-00163 Open

Algebraicity of joint spectral radii from rational input

DS · algebraic numbers · joint spectral radius · OpenProblemsInNLA

OP-00164 Open

Temporal regularity of marginal matrix-product growth

DS · growth rates · joint spectral radius · matrix products · OpenProblemsInNLA

OP-00165 Open

Symmetric maximizers for Lyapunov operators of order six

NA · Lyapunov operators · OpenProblemsInNLA · singular values

OP-00166 Partially resolved

Critical exponent for generalized doubly nonnegative matrices

NA · critical exponents · matrix powers · nonnegative matrices · OpenProblemsInNLA

OP-00167 Open

Decidability of zero hitting by rational matrix powers

NT · decidability · linear recurrence sequences · OpenProblemsInNLA · Skolem problem

OP-00168 Open

Decidability of zero hitting by a matrix exponential

NT · continuous Skolem problem · decidability · exponential polynomials · OpenProblemsInNLA

OP-00169 Partially resolved

Optimal pivot count for RPCholesky trace approximation

NA · low-rank approximations · Nyström approximations · OpenProblemsInNLA · pivoted Cholesky factorizations

OP-00170 Partially resolved

Optimal trace-estimation complexity using Kronecker matrix-vector queries

NA · Kronecker products · OpenProblemsInNLA · query complexity · trace estimation

OP-00171 Partially resolved

Optimal query complexity of spectral rank-k approximation

NA · Krylov subspace methods · low-rank approximations · OpenProblemsInNLA · query complexity

OP-00172 Open

Query complexity from Schatten to spectral norms

NA · low-rank approximations · OpenProblemsInNLA · query complexity · Schatten norms

OP-00173 Open

Super-exponential decay of the zero-permanent probability

PR · anticoncentration · OpenProblemsInNLA · permanents · random matrices

OP-00174 Partially resolved

Minimum linear measurements for uniform recovery of real low-rank matrices

NA · determinantal varieties · linear measurements · low-rank matrix recovery · OpenProblemsInNLA

OP-00175 Partially resolved

The Goreinov–Tyrtyshnikov–Zamarashkin conjecture on square-submatrix inverse norms

NA · column subset selection · OpenProblemsInNLA · pseudoskeleton approximations

OP-00176 Open

Constant-factor HSS approximation in polynomial time

NA · approximation algorithms · hierarchical matrices · HSS matrices · OpenProblemsInNLA

OP-00177 Open

HSS approximation from a number of matvecs independent of depth

NA · HSS matrices · matrix-vector queries · OpenProblemsInNLA · sketching

OP-00178 Partially resolved

Optimal matvec query complexity of HODLR approximation

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

OP-00179 Partially resolved

Sharp gap between volume sampling and the worst matrix with a prescribed spectrum

NA · column subset selection · Nyström approximations · OpenProblemsInNLA · volume sampling

OP-00180 Open

Exact bilinear rank of the 3×3 matrix product

AG · bilinear complexity · matrix multiplication · OpenProblemsInNLA · tensor rank

OP-00181 Partially resolved

Minimal asymptotic rank of the small Coppersmith–Winograd tensor

AG · asymptotic rank · Coppersmith–Winograd tensors · matrix multiplication · OpenProblemsInNLA

OP-00182 Open

Explicit tensors with quadratic border rank

AG · border rank · explicit tensors · OpenProblemsInNLA

OP-00183 Open

Scholz–Brauer inequality for multiplication chains

NT · addition chains · exponentiation · OpenProblemsInNLA

OP-00184 Open

Deterministic polynomial-time commutative Edmonds problem

NA · derandomization · OpenProblemsInNLA · polynomial identity testing · symbolic determinants

OP-00185 Partially resolved

The least positive permanent of a sign matrix

CO · OpenProblemsInNLA · permanents · sign matrices

OP-00186 Partially resolved

Realizing every sign-matrix permanent with negative entries confined on or above the diagonal

CO · OpenProblemsInNLA · permanents · sign matrices

OP-00187 Open

Deterministic near-quadratic matrix multiplication verification

NA · derandomization · matrix multiplication · OpenProblemsInNLA

OP-00188 Open

Cryer's Hadamard complete-pivoting conjecture

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

OP-00189 Open

The exact fifth complete-pivoting growth factor

NA · Gaussian elimination · growth factors · OpenProblemsInNLA

OP-00190 Partially resolved

Precision required for conjugate gradients to attain backward accuracy in n steps

NA · backward errors · conjugate gradient methods · OpenProblemsInNLA · rounding errors

OP-00191 Open

RILU conditioning for the Neumann problem on smooth planar domains

NA · condition numbers · incomplete factorizations · OpenProblemsInNLA · preconditioners

OP-00192 Open

Perturbed MILU conditioning for Neumann problems in two and three dimensions

NA · condition numbers · incomplete LU factorizations · OpenProblemsInNLA · preconditioners

OP-00193 Partially resolved

Spectral disk for a Radau stage preconditioner

NA · eigenvalue bounds · OpenProblemsInNLA · preconditioners · Runge–Kutta methods

OP-00194 Partially resolved

Positive diagonal preconditioning with a nilpotent stiff limit

NA · collocation methods · diagonal preconditioners · OpenProblemsInNLA · Runge–Kutta methods

OP-00195 Partially resolved

Exploit spectral outliers without losing input sparsity

NA · OpenProblemsInNLA · randomized algorithms · singular values · sparse linear systems

OP-00196 Partially resolved

Polynomial-time solution under the regularity promise

NA · absolute value equations · linear complementarity problems · OpenProblemsInNLA · P-matrices

OP-00197 Open

Polynomial-time deterministic restricted isometries with nearly linear row count

FA · compressed sensing · explicit constructions · OpenProblemsInNLA · restricted isometry property

OP-00198 Partially resolved

Sharp sample complexity for restricted isometries from the cyclic Fourier matrix

FA · compressed sensing · OpenProblemsInNLA · restricted isometry property · subsampled Fourier matrices

OP-00199 Partially resolved

Complex equiangular tight frames with twice the dimension

FA · conference matrices · equiangular tight frames · line packings · OpenProblemsInNLA

OP-00200 Partially resolved

The minimum number of quadratic measurements for generalized phase retrieval

FA · OpenProblemsInNLA · phase retrieval · projective spaces · quadratic measurements