Paper VIII: Exact low rank algebra and recompression

5 Exact low rank algebra and recompression

On this page · Permalink · Source line 656

A regular diagonal packet structure is coupled by global low rank factors.

5.1 Products and inverses

On this page · Permalink · Source line 665

Theorem 5.1: Exact BDLR product

Let

\[ A=D_A+U_AV_A^*, \qquad B=D_B+U_BV_B^* \]

use the same diagonal packet layout. Then

\[ AB=D_AD_B+U_CV_C^*, \]

where

\[ U_C = \begin{bmatrix} D_AU_B+U_A(V_A^*U_B)&U_A \end{bmatrix} \]

and

\[ V_C = \begin{bmatrix} V_B&D_B^*V_A \end{bmatrix}. \]

The unrecompressed correction rank is at most \(r_A+r_B\).

Read proof · Visual guide: The cross term has somewhere to go · Visual guide: Close the loop on the running example · Read statement and proof side by side · Permalink · Source line 667 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 5.1

Expand the product:

\[ AB = D_AD_B +D_AU_BV_B^* +U_AV_A^*D_B +U_A(V_A^*U_B)V_B^*. \]

The second and fourth terms share the right factor \(V_B^*\). The third term equals

\[ U_A(D_B^*V_A)^*. \]

Concatenation gives the stated factors.

Back to statement · Read statement and proof side by side · Permalink · Source line 697 · Claim record · Lean coverage · Code · Worked examples

Corollary 5.2: Rank growth in a product chain

Let

\[ A_j=D_j+U_jV_j^*, \qquad j=1,\ldots,m, \]

share one diagonal packet layout. Before recompression, the product

\[ A_m\cdots A_1 \]

has a BDLR representation whose correction rank is at most

\[ \boxed{ \sum_{j=1}^m r_j. } \]

Read proof · Visual guide: The cross term has somewhere to go · Read statement and proof side by side · Permalink · Source line 714 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary 5.2

Apply Theorem 5.1 inductively. Each new factor adds at most its own correction rank.

Back to statement · Read statement and proof side by side · Permalink · Source line 733 · Claim record · Lean coverage · Code · Worked examples

Theorem 5.3: Woodbury inversion

Assume \(D\) and

\[ S=I+V^*D^{-1}U \]

are invertible. Then

\[ \boxed{ (D+UV^*)^{-1} = D^{-1} -D^{-1}US^{-1}V^*D^{-1}. } \]

Read proof · Visual guide: A large inverse, a small denominator · Read statement and proof side by side · Permalink · Source line 737 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 5.3

Multiply the proposed inverse by \(D+UV^*\). The coefficient of \(V^*D^{-1}\) is

\[ U-US^{-1}(I+V^*D^{-1}U)=0. \]

The remaining term is the identity. The right inverse calculation is the same.

Back to statement · Read statement and proof side by side · Permalink · Source line 753 · Claim record · Lean coverage · Code · Worked examples

The formula and its history are discussed in [Hager1989]. It reduces one large solve to packet solves with \(D\) and one dense solve with the small matrix \(S\).

Permalink · Source line 761

Corollary 5.4: Inverse norm bound

Under the hypotheses of Theorem 5.3,

\[ {\left\lVert(D+UV^*)^{-1}\right\rVert} \leq {\left\lVert D^{-1}\right\rVert} + {\left\lVert D^{-1}U\right\rVert} {\left\lVert S^{-1}\right\rVert} {\left\lVert V^*D^{-1}\right\rVert}. \]

Read proof · Visual guide: A large inverse, a small denominator · Read statement and proof side by side · Permalink · Source line 763 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary 5.4

Apply the triangle inequality and submultiplicativity to the Woodbury formula.

Back to statement · Read statement and proof side by side · Permalink · Source line 776 · Claim record · Lean coverage · Code · Worked examples

5.2 Optimal factor recompression

On this page · Permalink · Source line 780

Standard fact 5.5: Eckart Young Mirsky theorem

If \(M\) has singular values

\[ \sigma_1\geq\sigma_2\geq\cdots, \]

pad this finite sequence with zeros. For each integer \(k\ge0\), its truncated singular value decomposition \(M_k\) is a best rank-at-most-\(k\) approximation. It satisfies

\[ {\left\lVert M-M_k\right\rVert}_2=\sigma_{k+1} \]

and

\[ {\left\lVert M-M_k\right\rVert}_{\rm F} = \left( \sum_{j>k}\sigma_j^2 \right)^{1/2}. \]

Permalink · Source line 782 · Claim record · Lean coverage · Code · Worked examples

This is classical [EckartYoung1936], [Mirsky1960]. The next theorem shows that an \(n\) dimensional singular value decomposition is unnecessary when a correction is already factored.

Permalink · Source line 801

Theorem 5.6: Small core recompression

Let

\[ L\in{\mathbb C}^{m\times r}, \qquad R\in{\mathbb C}^{n\times r}. \]

Take compact QR factorizations

\[ L=Q_LR_L, \qquad R=Q_RR_R, \]

where the columns of \(Q_L\) and \(Q_R\) are orthonormal. Form the small core

\[ G=R_LR_R^* \]

and let

\[ G=W\Sigma Z^* \]

be an ordered thin singular value decomposition, with nonnegative nonincreasing singular values. For an integer \(k\ge0\), retain \(\min\{k,d\}\) columns, where \(d\) is the number of supplied thin singular directions; tail singular values beyond \(d\) are zero. Define

\[ L_k=Q_LW_k\Sigma_k^{1/2}, \qquad R_k=Q_RZ_k\Sigma_k^{1/2}. \]

Then

\[ L_kR_k^* \]

is a best rank at most \(k\) approximation to \(LR^*\). Its spectral and Frobenius errors are the singular value tails in Standard fact 5.5. The core dimensions equal the column ranks of the two input factors. A noncompact reduced QR may retain extra zero singular directions without changing the conclusion.

Read proof · Visual guide: Stored width is not intrinsic rank · Visual guide: Why a core optimum is global · Visual guide: A complex range needs an adjoint · Read statement and proof side by side · Permalink · Source line 803 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 5.6

The exact factor product is

\[ LR^* = Q_LGQ_R^*. \]

The two outer maps are isometries on their column spaces. They preserve the nonzero singular values and the spectral and Frobenius norms of the core. For every ambient rank-at-most-\(k\) competitor \(B\), its compression \(Q_L^*BQ_R\) has rank at most \(k\), and compression cannot increase either norm. Thus the core best-approximation inequality also lower-bounds the error of every ambient competitor. Truncating the singular value decomposition of \(G\) and applying Standard fact 5.5 gives the result. The compact QR dimensions equal the ranks of the factor column spaces.

Back to statement · Read statement and proof side by side · Permalink · Source line 837 · Claim record · Lean coverage · Code · Worked examples

The approximation decision is made from the singular values of a small core whose dimension is the unrecompressed rank.

Remark 5.7

The large matrices enter through QR factorizations of the factors. The singular value problem has dimension at most the unrecompressed rank. Updating and recompressing low rank factors is standard numerical linear algebra [GolubKahan1965], [BunchNielsen1978].

Permalink · Source line 854

Theorem 5.8: Product chain perturbation

Let \(A_1,\ldots,A_m\) be exact factors and let

\[ \widehat A_j=A_j+E_j. \]

Then

\[ \boxed{ \left\| \widehat A_m\cdots\widehat A_1 - A_m\cdots A_1 \right\| \leq \sum_{j=1}^m \left( \prod_{i=j+1}^m{\left\lVert\widehat A_i\right\rVert} \right) {\left\lVert E_j\right\rVert} \left( \prod_{i=1}^{j-1}{\left\lVert A_i\right\rVert} \right). } \]

Empty products are one.

Read proof · Visual guide: Errors enter at different places · Read statement and proof side by side · Permalink · Source line 858 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 5.8

Use the telescoping identity

\[ \widehat A_m\cdots\widehat A_1 -A_m\cdots A_1 = \sum_{j=1}^m \widehat A_m\cdots\widehat A_{j+1} E_j A_{j-1}\cdots A_1. \]

Take norms term by term.

Back to statement · Read statement and proof side by side · Permalink · Source line 885 · Claim record · Lean coverage · Code · Worked examples

Theorem 5.9: Certified repeated recompression

Let

\[ P_0=I, \qquad P_j=A_jP_{j-1}, \]

be exact partial products. Suppose an implemented chain satisfies

\[ \widehat P_0=I, \qquad \widehat P_j = A_j\widehat P_{j-1}+E_j, \]

where \(E_j\) is the additive error introduced after the \(j\)th multiplication, for example by factor recompression. Then

\[ \boxed{ {\left\lVert\widehat P_m-P_m\right\rVert} \leq \sum_{j=1}^{m} \left( \prod_{i=j+1}^{m}{\left\lVert A_i\right\rVert} \right) {\left\lVert E_j\right\rVert}. } \]

If \({\left\lVert E_j\right\rVert}\leq\delta_j\), the same formula with \(\delta_j\) gives a certified final error.

Read proof · Visual guide: Errors enter at different places · Read statement and proof side by side · Permalink · Source line 899 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 5.9

Set \(D_j=\widehat P_j-P_j\). Then

\[ D_j=A_jD_{j-1}+E_j, \qquad D_0=0. \]

Repeated substitution gives

\[ D_m = \sum_{j=1}^{m} A_mA_{m-1}\cdots A_{j+1}E_j. \]

Taking norms yields the result.

Back to statement · Read statement and proof side by side · Permalink · Source line 929 · Claim record · Lean coverage · Code · Worked examples

Source and conversion record

Source SHA-256: ef616bca9291ac766d492b88f3166be4bc2b39f9ba6034dea3a4bcf2d2bf5d7f

Unsupported prose commands stop the build. The mathematical expression sequence is checked against the source, with manuscript macros expanded for display.

Conversion records

Read and explore

Proofs and implementation

About this work

Other resources