Because exact preconditioning via full eigendecomposition is computationally prohibitive, a significantly cheaper alternative is to approximate the distortion by rescaling the problem using only the diagonal entries of the matrix $$\mathbf{Q}$$. This diagonal preconditioning calculates a new matrix $$\tilde{\mathbf{Q}} = \textrm{diag}^{-\frac{1}{2}}(\mathbf{Q}) \mathbf{Q} \textrm{diag}^{-\frac{1}{2}}(\mathbf{Q})$$. In this rescaled representation, the entries become $$\tilde{\mathbf{Q}}_{ij} = \mathbf{Q}_{ij} / \sqrt{\mathbf{Q}_{ii} \mathbf{Q}_{jj}}$$, ensuring that every diagonal element $$\tilde{\mathbf{Q}}_{ii} = 1$$. In many scenarios, particularly when the problem is roughly axis-aligned, this straightforward rescaling considerably reduces the condition number without the massive cost of computing true eigenvalues.

Diagonal Preconditioning Approximation

To alleviate the severe optimization difficulties caused by a large condition number, one theoretical solution is to distort the objective space so that all eigenvalues equal $$1$$. This exact preconditioning technique requires the eigenvalues and eigenvectors of $$\mathbf{Q}$$ to rescale the problem from the variable $$\mathbf{x}$$ to a new coordinate system defined as $$\mathbf{z} \stackrel{\textrm{def}}{=} \boldsymbol{\Lambda}^{\frac{1}{2}} \mathbf{U} \mathbf{x}$$. In this transformed space, the quadratic term $$\mathbf{x}^\top \mathbf{Q} \mathbf{x}$$ elegantly simplifies to $$||\mathbf{z}||^2$$. However, this strategy is highly impractical because computing exact eigenvalues and eigenvectors is generally far more computationally expensive than solving the actual problem itself.

Claude

The condition number of an optimization problem, denoted as $$\kappa$$, is defined as the ratio between the largest and the smallest eigenvalue of the problem's defining matrix (such as the Hessian or $$\mathbf{Q}$$ in a quadratic objective). It is mathematically expressed as $$\kappa = \frac{\boldsymbol{\Lambda}_1}{\boldsymbol{\Lambda}_d}$$. When the condition number is large, indicating that some eigenvalues are significantly larger than others, the problem becomes exceedingly difficult to solve accurately because coordinates associated with small eigenvalues can experience dramatic, unstable changes, requiring optimization algorithms to carefully manage a large dynamic range of values.

Learn Before

Related

Learn After