Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Equality-constrained least-squares — where it appears

Minimising the norm of a residual subject to a set of equations that must hold exactly. Its optimality conditions are a saddle-point system, and it is also the limit of an unconstrained problem in which the equations are given a weight that grows without bound.

Named by 8 essays across 2 fields — each of them below, with the objects they name alongside it.

0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴4.8·10⁻¹⁵normal equations14Gram–Schmidt4.9·10¹⁰1/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is

A constraint is a weight at infinity

Stack an equality constraint on top of a least-squares problem with a large weight and the answer approaches the constrained one like 1/τ². The limit is takeable to any accuracy — and how far it can be taken is a property of the solver, not of the problem. One of them stops at the square root of the precision, and one of them does not stop.

leastsquares · Constrained least-squares 2468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²log₁₀ τ‖Bx − d‖ / ‖d‖sketched with the objectiveweighted, not sketchedkept out of the sketchone power instead of twokept out — feasibility1.7·10⁻¹⁶sketched at τ = 10⁸1.7·10⁻⁸unsketched at τ = 10⁸1.7·10⁻¹⁶objective ÷ optimum1.2a sketch preserves a normand a constraint is not one

The half of a problem a sketch may touch

A sketch guarantees that a norm is preserved to within a factor. An equality constraint is a statement that a quantity is zero, and no multiplicative guarantee says anything about zero. Sketch a constrained problem written as a weighted one and the constraint is not destroyed — it is demoted, from a violation of 1/τ² to one of ε/τ, exactly half the exponent.

randomised · Sketching 10¹10³10⁵10⁷10⁹10¹¹10¹³10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹κ(B), the conditioning of the constraint blockrelative error, and feasibilitydashes: the method of weightingthe saddle-point routethe null-space routealong the bottom: how nearly every answer satisfies the constraintsfeasible and wrongκ(B)4.6·10¹²κ(B)·u0.001null space1.2·10⁻⁴saddle point0.0082weighting2.6feasibility10⁻¹⁵every constraint is satisfiedand the answer has no digits

Feasible and wrong

A third constraint that nearly repeats the first takes the best route's answer from 2.96·10⁻¹⁵ to 1.16·10⁻⁴, and the other two routes to no correct digit at all. Every one of those answers satisfies every constraint to 10⁻¹⁵. The quantity a caller checks after a constrained solve is the one quantity here that says nothing.

leastsquares · Constrained least-squares 10³10⁶10⁹10¹²10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹κ(A), identical for both problemsrelative error in the answerthe weak directions in the constraint's null spacethe weak directions in the constraint's own rowsone κ(A), two problemsκ(A), both10¹²κ left, constrained1κ left, free10¹²error, constrained4.7·10⁻¹⁶error, free3·10⁻⁴between them6.4·10¹¹a constraint is informationand κ(A) does not know it arrived

The condition number that does not know

Two constrained fits with the same size, the same number of constraints and the same κ(A) to twelve figures. One returns 4.7·10⁻¹⁶ and the other 3.0·10⁻⁴. What separates them is the conditioning of A restricted to the constraint's null space — 1.00 against 10¹² — which every solver computes on the way and none reports.

leastsquares · Constrained least-squares 10¹10³10⁵10⁷10⁹10¹¹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1κ(A), the conditioning of the fitrelative error in the answerthe saddle-point route, in floating pointdashes: forming AᵀA, then solving exactlythe method of weighting, τ = 10⁸the null-space routethe reference was a methodκ(A)10¹¹κ of what is left4.9·10⁶null space1.9·10⁻⁹saddle point4.6·10⁻⁴forming AᵀA alone3.4·10⁻⁴weighting3·10⁻⁹the damage is in the formingand not in the solving

The reference was a method

The optimality conditions of a constrained fit contain AᵀA, so solving them is the road that squares the problem wearing a block structure. At κ(A) = 10¹¹ the route that never forms a cross-product returns 1.89·10⁻⁹ and the route that does returns 4.64·10⁻⁴ — and forming AᵀA and then solving it in exact rationals returns 3.45·10⁻⁴, so nearly all of the loss happens before any elimination begins.

leastsquares · Constrained least-squares same κ(B), two right-hand sides‖λ‖ ÷ κ(B), asking0.0081‖λ‖ at κ(B) = 10⁶·⁷, consistent0.00410¹10³10⁵10⁷10⁹10¹¹10¹³10⁻³10⁻¹10¹10³10⁵10⁷10⁹10¹¹κ(B), the conditioning of the constraint block‖λ‖, the multipliers' sizethird constraint asksasks nothing∝ κ(B)the same B at every point, two values of d₃the multipliers read the right-hand side

A multiplier is a force

A third constraint nearly parallel to the first made the multipliers of a constrained fit rise in exact proportion to κ(B), which looked like the conditioning measured a second, dearer way. It was not. Give the third constraint a datum that asks for nothing new and, at the same κ(B) = 4.6·10¹², the multipliers are eighteen thousand times smaller; give it a strain δ and they are 0.0133 δ/ε², a force on a lever of length ε. What they measure is what the constraint asks. What they do not measure is the error of the best route, which sits at the same level whether the constraint asks for nothing or for a displacement of 3·10⁹.

leastsquares · Constrained least-squares error at the largest strainas given4.6·10⁻⁴multipliers to the size of x3.3·10⁻⁸first-solve scale, never below one1.8·10⁻⁸null-space route1.8·10⁻⁸10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³strain δ (left: none)relative error in x10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²noneas givenmultipliers to the size of xfirst-solve scale, never below onenull-space routethe loss was the multipliers' sizeand it scales away

The scale that only moved a pivot

Multiply the constraint rows of a saddle-point system until its multipliers are the size of its solution, and the extra error the route was blamed for — 4.6·10⁻⁴ against the null-space route's 1.8·10⁻⁸ — falls to 3.3·10⁻⁸. The prediction holds and its reason does not. A scale of ten does what a scale of 6·10⁵ does; hold the elimination's row order fixed and nine decades of scale move the error by less than a factor of five. What the scale changed was which row partial pivoting took at the second step, and taking the constraint rows first does the same job with no scale at all.

leastsquares · Constrained least-squares predicted against measuredproblems49worst relative difference4.4·10⁻¹⁶1.522.533.5coupling, from one to ten to the minus twelveswitching scale11e-21e-41e-61e-81e-101e-12repeatedconsistentstrainedrings: predictedevery dot inside its ringone elimination tells the switch

The switch is read before the solve

Scaling the constraint rows of a saddle-point system rescued the route to a constrained least-squares fit by changing which row partial pivoting takes at the second step. The scale at which it changes can be read before anything is solved: scaling multiplies every constraint row's candidate by s and leaves every other row's alone, so one unscaled elimination, recording the two kinds of candidate at each step, gives the switch exactly — on all forty-nine problems, to within one part in 10¹⁵ of what bisection finds, decided at the second step everywhere but at a coupling of one. A scale just past it removes the catastrophe where there was one. It does not make the route as good as eliminating the constraints first: on four problems every scale tried is thirty to thirty-nine times worse, and they are the problems where the unscaled route was too.

leastsquares · Constrained least-squares

Named alongside it

The objects these essays reach for when they reach for this one.

Saddle-point systemsExact ground truthCondition numberQR factorisationLagrange multiplierMethod of weightingElimination orderLeast-squaresNormal equationsNull-space basisNull-space methodPartial pivoting

All concepts