Odd-order Kikuchi Hessian optimality conjecture
Statement
Let be odd and fix an integer . For with and with , define the rectangular symmetric-difference matrix by
Let be a unit-norm top left singular vector of , let be the corresponding top right singular vector, and define the recovery output by . Odd-order Kikuchi Hessian optimality conjecture. In the Rademacher-spiked tensor model with odd , if
then there is a threshold such that thresholding the top singular value of at achieves strong detection, and the stated singular-vector algorithm achieves strong recovery. The conjecture asserts that this odd-order Kikuchi Hessian algorithm matches the performance of sum-of-squares; only sub-optimal results for this algorithm are known in the paper, while optimal results are proved for a related algorithm.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.