Modern speech codecs based on Code Excited Linear Prediction (CELP) employ an analysis-by-synthesis optimization loop to find the best quantization of the source model parameters. With this approach, optimal quantization can be achieved only with an exhaustive search. Instead, we propose to use matrix factorization to decorrelate the objective function of the optimization problem, whereby the computationally expensive iteration can be avoided and optimal performance is guaranteed. We compare two factorizations of the autocorrelation matrix, the eigenvalue decomposition and Vandermonde factorization. Our experiments show that decorrelation improves perceptual SNR and gives a large reduction in computational complexity, mostly without significant impact on subjective quality.