Linear-time positive definite Hankel factorization conjecture

Let HRn×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

HBBF<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 BBCC\mathbf{B}\mathbf{B}^*-\mathbf{C}\mathbf{C}^*.

Sources & referencesView supporting material

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.