Is it a new objective function?

No. It is a way to represent and manipulate the matrix used by an optimization method.

Does it necessarily lose precision?

It is algebraically exact for its specified updates; floating-point implementation and deliberate history truncation introduce separate considerations.

Is M always positive definite?

No. Even a positive-definite represented matrix can use an indefinite correction matrix, as the example shows.

AI Glossary / Mathematics and optimization / Advanced

Compact quasi-Newton representation

Definition

A compact quasi-Newton representation expresses a curvature-approximation matrix as a simple starting matrix plus a correction assembled from a small collection of vectors and a small matrix. It allows optimization software to use the represented matrix without storing every entry. The representation is especially useful when the number of retained updates is small relative to the number of variables.

What it means

Quasi-Newton methods learn curvature from changes in parameters and gradients. A full approximation can contain billions of entries when there are many parameters. Yet each update may change that matrix only through a low-rank correction.

The compact representation exposes that structure. Instead of treating the result as an unstructured dense array, it retains the information needed to reconstruct or apply the correction. “Compact” describes an algebraic representation, not compressed decimal precision. Within exact arithmetic, it can represent the corresponding sequence of retained quasi-Newton updates exactly.

How it works

A common form is B=B₀+ΨMΨᵀ. Here B₀ is an easily applied initial matrix, Ψ has many rows but relatively few columns, and M is a small matrix. The specific formulas depend on the quasi-Newton update family.

For BFGS, stored displacement vectors form S and stored gradient-change vectors form Y. One compact construction uses Ψ=[B₀S,Y], with M determined by inner products involving those histories. With m retained rank-two updates, Ψ has 2m columns.

To multiply by a vector v, calculate Ψᵀv, apply M to that small intermediate vector, multiply by Ψ, and add B₀v. Linear solves, spectral calculations and constrained-optimization operations can exploit related small-matrix structures. A compact inverse-Hessian representation is a separate formula; inverting M alone does not invert the complete matrix B.

Three practical examples

1. Large optimization: apply a limited-history curvature approximation when forming an n-by-n dense matrix would consume too much memory.

2. Bound-constrained methods: work with restricted or projected curvature information using structured representations rather than repeatedly assembling a full matrix.

3. Trust-region calculations: exploit a simple base matrix plus low-rank correction when examining eigenvalues or solving suitable subproblems, with safeguards appropriate to the update family.

Think of it this way

Think of maintaining a base document plus a short set of structured edits instead of saving an entirely new copy after each edit. The combination defines the current document, and operations can sometimes use the edits directly.

The analogy is limited: matrix updates interact algebraically, so the small matrix M records more than an arbitrary list of independent changes. Discarding history is also a deliberate modeling choice, not always lossless compression of the entire earlier optimization process.

Worked example

Consider an original two-variable BFGS update with B₀=I, displacement s=(1,0) and gradient change y=(2,1). The curvature product yᵀs=2 is positive. The update is B=I−ssᵀ+(yyᵀ)/2, giving B=[[2,1],[1,1.5]].

A compact form uses Ψ=[s,y]=[[1,2],[0,1]] and M=diag(−1,0.5). Then ΨMΨᵀ subtracts ssᵀ and adds yyᵀ/2, exactly reproducing the update.

Apply this representation to v=(1,2). First Ψᵀv=(1,4). Next M(1,4)=(−1,2). Multiplying by Ψ gives (3,2). Adding B₀v=(1,2) produces Bv=(4,4). Direct multiplication by the explicit B gives the same answer.

Notice that M is indefinite even though B is positive definite: B has positive first leading entry 2 and determinant 2. The correction factors alone do not determine the definiteness of the full matrix.

For scale intuition, a dense 100,000-by-100,000 matrix contains ten billion entries, or about 80 GB at eight bytes per entry. Two histories S and Y with ten vectors each contain two million entries, about 16 MB, before additional working storage. This is an illustrative storage count, not a measured solver footprint.

Illustrative case study

Fictional case: an engineering team calibrates a high-dimensional smooth model. A dense curvature matrix exceeds its available memory, so the team implements a limited-memory compact representation with a simple diagonal base.

On a small test problem, engineers explicitly build the update matrix and compare several matrix-vector products with the compact calculation. They then test the history-replacement policy and small-system conditioning before scaling up. The report distinguishes memory savings from convergence quality: retaining fewer updates may change the optimization trajectory even when every compact operation is implemented correctly.

Common misconceptions and mistakes

Do not equate compact representation with a sparse full matrix. The represented matrix may be dense while its correction has a short factorization.

Do not confuse a low-rank correction with a low-rank entire matrix. Adding a nonsingular base can produce a full-rank result.

Do not use the formula from one update family for another without deriving the corresponding M. Check denominator and curvature conditions. Explicit inverses displayed in mathematics are often implemented through appropriate factorizations or solves; a small matrix can still be ill-conditioned.

Business use

The practical value is making richer curvature information affordable in optimization systems. Benefits depend on the cost of applying B₀, the retained history size and the operations the solver needs.

Benchmark against the required alternative, such as a standard two-loop L-BFGS product or a direct small-problem implementation. Count working memory, setup costs and numerical accuracy as well as storage of S and Y. Avoid claiming that the compact representation alone supplies a better model, a global optimum or faster convergence.

Check your understanding

Why does a correction built from two vectors not imply that a large represented matrix has rank at most two?

Answer: Those vectors describe the correction to B₀. The rank of the full matrix depends on the base plus that correction; in larger dimensions a full-rank base can remain full rank.

Related terms

Trust region
quasi-Newton method
BFGS
L-BFGS
low-rank update
Hessian approximation
matrix-vector product
numerical conditioning

Learn next

verify B₀+ΨMΨᵀ for one update by expanding the products, then implement its action on a vector without forming B. Study how compact BFGS and compact symmetric rank-one formulas differ.

Sources

Sources: DeGuchy, Erway and Marcia, “Compact Representation of the Full Broyden Class of Quasi-Newton Updates,” primary introduction and Section 2 formulas read: https://arxiv.org/pdf/1705.08306 . This paper identifies the foundational Byrd–Nocedal–Schnabel representation and distinguishes update families. Examples and storage arithmetic are original and hand-checked; no software benchmark is claimed.

Previous: Compact model Next: Compact-support kernel