Low-Rank Denoising for Predict-then-Optimize

A shortest-path decision is often made from edge costs that are only observed through noisy samples, such as the average of $m$ simulation replications. When the mean cost vectors of different instances lie near a $k$-dimensional subspace, projecting the averaged sample onto that subspace should remove noise. We make this precise. The mean squared error of any projection estimator splits exactly into a variance term and a bias term. The best projector is the positive eigenspace of $\Sigma_c - D/m$, where $\Sigma_c$ is the covariance of the true costs and $D$ is the noise covariance. For a rank-$k$ signal, the projection has the error of a sample mean with a factor $d/(\mu k)$ more replications, where $d$ is the number of edges and $\mu$ is an incoherence constant. For a signal that is only approximately low-rank, every rank-$k$ projection has an error floor, and the plain average wins beyond an explicit replication count. A margin bound shows that the chance of choosing a suboptimal path falls at the same improved rate. A projector learned from $n$ noisy instances loses at most an $O(d/n)$ term.