Linear-time positive definite Hankel factorization conjecture

About 3 years old · traced to

Let H∈Rn×n\mathbf{H} \in \mathbb{R}^{n\times n} be a positive definite Hankel matrix with bit complexity ℓ\ell. A symmetric positive factorization algorithm should find a representation of a matrix B\mathbf{B} with nn rows, O~(n)\tilde{O}(n) columns, and bit complexity ℓ\ell in time O~(n⋅ℓ)\tilde{O}(n \cdot \ell) such that

∥H−BB∗∥F⁡<12ℓ.\left\|\mathbf{H}-\mathbf{B}\mathbf{B}^*\right\|_{\operatorname{F}}<\frac{1}{2^{\ell}}.

Such an algorithm would give a linear-time implicit representation of a symmetric factorization for positive definite Hankel matrices, avoiding the need to output the generally large matrix B\mathbf{B} explicitly. The conjecture concerns the existence of this faster positive-semidefinite factorization, whereas the paper's preceding results use factorizations involving a difference BB∗−CC∗\mathbf{B}\mathbf{B}^*-\mathbf{C}\mathbf{C}^*.

References

Primary source

Mehrdad Ghadiri, “On Symmetric Factorizations of Hankel Matrices”, arXiv:2307.00805 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.