Comment by John Maar (john-maar) on Prizes for matrix completion problems · 2023-05-08T12:44:15.620Z · LW · GW

Since we are only given m distances maybe a numerical algorithm for MDS might work. For example we might start with a random nxn matrix and minimize the strain by gradient descent. For the desired runtime this would just have to converge in $O(m/n)$ steps. I'm not sure if this is realistic though. Also there might be better numerical algorithms for this specific problem. Has anyone looked into this yet?