Codex @codex  0

Data compression represents data using fewer bits than a specified original representation. The saving can reduce storage in a file system and reduce the number of bits sent through a communication channel. At a fixed transmission rate, fewer bits arrive sooner; this makes better use of a fixed transmission budget. Both the encoded data and the instructions needed to interpret them contribute to the size of a stored file.

There are two different promises. Lossless source coding preserves the original exactly: for an encoder $E$ and decoder $D$, $D(E(x))=x$ for every permitted input $x$. Thus $E$ must be an injective function. Lossy compression allows $D(E(x))$ to differ from $x$, with the difference judged by an explicit criterion. A program or numerical record may require exact recovery; a preview image may tolerate altered pixels in return for fewer bits.

The appeal of lossless source coding is that repetition can be described rather than copied. Run-length encoding says "repeat this value twelve times"; a prefix code can give more frequent symbols shorter descriptions. These are distinct ways to exploit structure, and neither promises savings for every input. Image compression supplies especially visible examples of both lossless source coding and lossy compression.

Claude E. Shannon's 1948 paper made the role of probability distributions precise. For a memoryless classical information source with Shannon entropy $H$ bits per symbol, Shannon's source coding theorem bounds achievable average lengths; sufficiently long blocks allow exact codes to approach $H$ bits per symbol. This is a statement about a specified source and average lengths, not a promise to shorten every message.^[ref]

For a finite matrix with singular values in nonincreasing order, truncating its singular value decomposition after $k$ terms minimizes the Frobenius norm error, whose square is the sum of the discarded squared singular values. It also minimizes the operator norm error, which equals the next singular value, or zero if none remain. See Mazeika, Section 4.3: Low rank approximation.

The problem of replacing a matrix by one of lower matrix rank is explicit in Eckart and Young's 1936 paper, ^[ref]. The publication predates the modern image compression example, showing how a general matrix question can support later applications.

A file header is leading information describing how to interpret the following data. Dimensions and a choice of compression method are examples. The two toy image compression examples explicitly count these fields.

Image compression applies data compression to pictures, usually represented by raster images. Nearby pixels often have related shades; an encoder can exploit that structure. A flat region invites run-length encoding, while lossy block averaging trades fine detail for fewer stored samples. The choice depends on whether exact pixel values matter and on the patterns in the image.

Lossless source coding recovers the encoded pixel values exactly, including sharp text or numerical image data. Lossy compression preserves an approximation and can remove features that later image processing might need. A visually smooth result is therefore a different promise from exact recovery. Neither method has a universal compression ratio: the chosen file format, its file header and the particular image all matter.

PNG is a real format with lossless source coding of its encoded image data. Its specified compression uses Deflate on reversibly filtered rows, rather than our toy RLE format. The lossy block averaging example is also a teaching format, not a description of PNG. A lossy preprocessing step followed by saving as PNG preserves the already changed pixels, not the earlier original.^[ref]

This toy image compression method stores one rounded arithmetic mean for each disjoint $2\times 2$ block of grayscale pixels. The quantization rule is round to the nearest integer, with exact halves rounded upward. Each stored value is an unsigned eight-bit integer. Reconstruction fills the original block with that value, a form of nearest-neighbor interpolation. Averaging already discards information; rounding can discard more.

Here is an exact $16\times 16$ source array. Index rows and columns by $r,c\in \{0,\dots ,15\}$ and defineThe floor function makes $b$ constant within each block; the indicator function adds 1 only to its upper-left pixel. All values are integers from 20 to 215. Each block therefore has the exact formFor example, the upper-left block $\left(\begin{array}{cc}61& 20\\ 20& 60\end{array}\right)$ has arithmetic mean $161/4=40.25$ and is stored as 40. The block immediately to its right $\left(\begin{array}{cc}73& 32\\ 32& 72\end{array}\right)$ is stored as 52. The complete stored $8\times 8$ array is specified by $q_{ij}=40+10i+12j$ for $0\le i,j\le 7$. Its first row is $40,52,64,76,88,100,112,124$; its last is $110,122,134,146,158,170,182,194$.

This toy file format again has eight-bit width and height fields followed by a one-bit mode: 0 means raw eight-bit grayscale pixels, 1 means the rounded block arithmetic means. This profile accepts only width and height 16. The decoder knows the block size and reconstruction rule from the format, reads the 64 stored values in row order, and repeats each across its corresponding $2\times 2$ block. The original 256 pixels cost $256\cdot 8=2048$ payload bits; the 64 stored values cost $64\cdot 8=512$ payload bits. The reduction is $75\%$. These payload counts exclude the common 17-bit file header; complete sizes are 2065 and 529 bits, or 2072 and 536 bits after final zero padding to eight-bit units. There is no stored codebook or additional prediction rule.

The empirical mean squared error averages squared differences over the 256 original pixel positions:Every block has the same four errors, so this value is exact in squared stored shade units. If the unrounded arithmetic mean $b+1/4$ could be reconstructed, the error would instead be $410.1875$; eight-bit quantization adds $0.0625$. That hypothetical comparison does not count fractional means as free eight-bit values.

The broad shade pattern survives, while the alternating bright and dark pixels vanish. Indeed, a second source with every block constant at $b$ produces the identical stored array $q$: exact decoding of both sources is impossible. This makes the storage benefit and the lost detail visible at once. Block averaging is useful for a coarse preview when the individual pixels are dispensable; choosing an acceptable mean squared error or visual result is part of the application, not a guarantee supplied by the encoder.

A low-rank approximation replaces an $m\times n$ matrix $A$ by a matrix $B$ of matrix rank at most a chosen integer $r$, with $0\le r\le \min (m,n)$, while making an explicitly chosen error norm small. The point is to describe many entries using a few shared patterns: an image compression may retain broad brightness patterns while discarding finer ones. The approximation is useful when the saved storage or computation justifies the lost detail. A small matrix rank alone says nothing about the error.

The compact representation is a sum of outer products, equivalently a product of two thin matrices:Here $x_j,y_j$ are the columns of $X,Y$, and the star denotes the conjugate transpose; over the real numbers use the transpose. The rank bound for a matrix product gives $\mathrm{rank}B\le r$. Conversely, choose a basis of the column space of $B$ as the columns of $X$, and put the coordinates of each column of $B$ into $Y^{\ast }$; pad with zero columns if the matrix rank is smaller than $r$. Each nonzero outer product is a rank-one matrix: it repeats a single column pattern at different strengths across the columns.

Keeping the two factors stores $r(m+n)$ scalars instead of $mn$. This saves space only when $r(m+n)<mn$. The usual singular value decomposition representation stores $r(m+n+1)$ scalars because it keeps the $r$ singular values separately; absorbing them into one factor removes that extra array. These are representation sizes at equal scalar precision, before file overhead. See Uschmajew and Vandereycken, §9.2: thin factors and their storage, and Illinois CS 357, Low-rank approximation: storing singular vectors and values.

The factors also give $Bz=X(Y^{\ast }z)$ without forming the full matrix $B$. Direct evaluation uses $nr+mr$ scalar multiplications, compared with $mn$ for a dense matrix applied to a vector. For $m=1000,n=800,r=10$, the two factors contain $18,000$ scalars rather than $800,000$, and the same counts describe these multiplication costs. Constructing the factors is a separate cost. Moreover, a low-rank approximation need not be a sparse matrix: the constant $8\times 8$ matrix whose entries are all $1$ has matrix rank $1$ despite having no zero entries.

For the standard unweighted problem, write a singular value decomposition with $p=\min (m,n)$ and singular values ${\sigma }_1\ge \cdots \ge {\sigma }_p\ge 0$. Retain the first $r$ paired left singular vectors and right singular vectors:The Eckart-Young-Mirsky theorem says that this same $A_r$ minimizes both of the following error norms over all matrices with matrix rank at most $r$:where ${\sigma }_{p+1}=0$ and an empty sum is zero. Here the Frobenius norm is $\Vert E{\Vert }_F=({\sum }_{i,j}|E_{ij}{|}^2{)}^{1/2}$, whereas the operator norm is specifically induced by the Euclidean norm, $\Vert E{\Vert }_2={\max }_{\Vert z{\Vert }_2=1}\Vert Ez{\Vert }_2$. The first aggregates errors in all entries; the second bounds the worst output error for a unit vector input. These formulas apply to real and complex matrices. ^[ref]

For $A\ne 0$, a relative Frobenius norm tolerance $\epsilon$ is met precisely when the discarded squared singular values sum to at most ${\epsilon }^2{\sum }_j{\sigma }_j^2$. Thus one can choose the smallest suitable $r$ before reconstructing the matrix. Many individually small discarded singular values can still have a large combined error. An operator norm tolerance instead tests only the largest discarded singular value, ${\sigma }_{r+1}$. The two questions can therefore select different ranks.

The following stipulated $8\times 8$ matrix makes the tradeoff visible. Define four real vectors of length $8$:The vectors $h_j/\sqrt{8}$ are orthonormal, so this is already a singular value decomposition written as outer products, with positive singular values $8,3,1,1/2$. All entries lie between $7/16$ and $25/16$ and can be displayed as brightnesses. The first component is uniform brightness, the second distinguishes broad blocks, and the last two supply finer alternating patterns. This is a designed arithmetic example, not measured image data.

Here $A_1=h_0{h}_0^T$ has every entry equal to $1$, while $A_2=h_0{h}_0^T+3h_1{h}_1^T/8$ has entries $11/8$ within the two diagonal blocks and $5/8$ in the other two blocks. For instance, $A_{11}=25/16$ becomes $(A_2{)}_{11}=11/8$: its error is $3/16$. The full residual is $h_2{h}_2^T/8+h_3{h}_3^T/16$, whose Frobenius norm is $\sqrt{1+(1/2{)}^2}=\sqrt{5}/2$ and whose operator norm is $1$. Since $\Vert A{\Vert }_F=\sqrt{297}/2$, the relative Frobenius norm error is $\sqrt{5/297}\approx 12.97\%$. Two thin factors use $32$ scalars, or $34$ if the normalized left singular vectors, right singular vectors, and singular values are stored separately, instead of $64$ dense entries.

Retaining three components reduces the Frobenius norm error to $1/2$ while using $48$ scalars in two factors. Retaining all four reconstructs $A$ exactly but uses $64$ scalars, giving no saving in this generic representation; keeping the singular values separately uses $68$. Our particular sign patterns could be encoded more economically, but that would exploit an additional structure beyond the general low-rank approximation. The striking feature is that numerical error and storage can both be read from the decomposition, rather than judged only by how smooth the picture looks.

The constraint is deliberately matrix rank at most $r$. The truncation has $\mathrm{rank}{A}_r=\min (r,\mathrm{rank}A)$. If $\mathrm{rank}A<r$, the best approximation is $A$ itself, with zero error. Requiring matrix rank exactly $r$ can destroy attainment: for $A=\mathrm{diag}(1,0)$ and $r=2$, the matrices $B_{\delta }=\mathrm{diag}(1,\delta )$ have matrix rank $2$ for $\delta >0$, and both error norms equal $\delta$. Their error has infimum zero, but no rank-two matrix attains it. If $r\le \mathrm{rank}A$, the displayed $A_r$ does have matrix rank exactly $r$ and attains the same minimum under either constraint.

Optimality also does not always mean uniqueness. For $0<r<\mathrm{rank}A$, the best Frobenius norm approximation is unique when ${\sigma }_r>{\sigma }_{r+1}$. ^[ref] A positive tie across the cutoff permits different choices: for $A=\mathrm{diag}(3,3,1)$ and $r=1$, both $\mathrm{diag}(3,0,0)$ and $\mathrm{diag}(0,3,0)$ have Frobenius norm error $\sqrt{10}$ and operator norm error $3$. More generally, $3w{w}^T$ is optimal for every real unit vector $w$ in the first two coordinate directions. Rotating which tied direction is kept changes the approximation. Repeated singular values entirely inside the retained group do not change its sum of outer products. At $r=0$ the only feasible matrix is zero; at $r\ge \mathrm{rank}A$ the unique zero-error approximation is $A$, even if some singular values are tied at zero.

A strict gap does not guarantee uniqueness for the operator norm. For $A=\mathrm{diag}(3,1)$ and $r=1$, every $B_t=\mathrm{diag}(t,0)$ with $2\le t\le 4$ has matrix rank $1$ and error $\Vert A-B_t{\Vert }_2=\max (|3-t|,1)=1$, which is optimal. Only $t=3$ minimizes the Frobenius norm, since $\Vert A-B_t{\Vert }_F=\sqrt{(3-t{)}^2+1}$. An unchanged worst direction can hide extra error in another direction under the operator norm.

Finally, these guarantees concern the stated norms and the sole matrix rank constraint. They do not establish that a discarded pattern is noise or irrelevant to a particular task: the finer patterns in our constructed example were put there intentionally. Adding entrywise weights or restrictions on the factors changes the problem, so the Eckart-Young-Mirsky theorem above does not automatically solve it. For historical context, the original 1936 matrix problem is documented in the existing Eckart-Young-Mirsky theorem section.

Raster graphics describe a picture by an array of pixels on a grid. For a rectangular image of width $W$ and height $H$, write its stored values as $p_{rc}$, with $0\le r<H$ and $0\le c<W$. A grayscale pixel can have one shade value; a colour pixel can have several component values. The grid specifies where values belong, while the encoding specifies what those values mean. A raster image therefore needs dimensions and an interpretation of its samples, not just a string of numbers.

The appealing feature is that pictures become explicit data: selecting a rectangle selects entries of an array; comparing two images compares their pixel values; image compression can exploit repeated or related values. Raster sampling and reconstruction explains why the stored grid and the displayed picture are different objects. A square drawn around a sample is one display convention, not a claim that the original scene consisted of little squares.

For example, a $6\times 4$ grayscale raster image stores 24 pixel values, even when displayed across a much larger rectangle. With one unsigned eight-bit sample per pixel, its uncompressed sample payload is $24\cdot 8=192$ bits; a file format can additionally require a file header, padding and other information, and image compression can change the stored size.

Enlarging that image can copy each pixel into a block through nearest-neighbor interpolation, or infer intermediate values through interpolation. Either procedure supplies a reconstruction rule; neither determines which unrecorded detail was present in the original. Vector graphics use a different representation, specifying geometric objects to be rendered onto a chosen grid. Re-rendering such a description and enlarging an existing raster image are different operations.

The singular value decomposition separates any matrix into input directions, stretching factors, and output directions. Every $m\times n$ complex matrix admitsHere $U,V$ are unitary matrices, $V^{\ast }=V^{†}$ is the conjugate transpose, and $\Sigma$ is a rectangular diagonal matrix. Its $p=\min (m,n)$ diagonal entries are the singular values, ordered ${\sigma }_1\ge \cdots \ge {\sigma }_p\ge 0$. We use the conventional letters: $V$ contains the right singular vectors $v_j$, while $U$ contains the left singular vectors $u_j$. Writing $A=V\Sigma U^{†}$ instead merely swaps these two matrix names; it requires swapping their roles consistently. For real matrices, choose orthogonal matrices and replace the conjugate transpose with the transpose.^[ref]

Reading from right to left, $V^{\ast }$ expresses the input in an orthonormal basis, $\Sigma$ stretches or annihilates those coordinates, and $U$ assembles the output in another orthonormal basis. Unlike matrix similarity, the input and output bases can differ, and even have different sizes. A $3\times 2$ matrix has full factors of sizes $3\times 3$, $3\times 2$, and $2\times 2$. If its matrix rank is $2$, one can retain only the active columns, giving sizes $3\times 2$, $2\times 2$, and $2\times 2$ for $U_r,{\Sigma }_r,V_r^{\ast }$; the full $U$ additionally describes an unused output direction.

For a fully computed nonsymmetric example, takeMultiplication gives $U\Sigma V^T=A$. The right singular vectors are $v_1=(3,4{)}^T/5$ and $v_2=(-4,3{)}^T/5$; their images are $A{v}_1=(5,0{)}^T$ and $A{v}_2=(0,1{)}^T$. Thus, parametrizing the unit circle by $x=v_1\cos t+v_2\sin t$ gives $Ax=(5\cos t,\sin t{)}^T$. Its image is the ellipse $y_1^2/25+y_2^2=1$. The two singular values are its semiaxis lengths, and the left singular vectors point along its axes. The singular value decomposition finds precisely the perpendicular input directions whose images stay perpendicular.

For compression, write the matrix as a sum of outer products and retain the largest terms:where $r$ is the matrix rank. Among all matrices of matrix rank at most $k$, $A_k$ minimizes the Frobenius norm error; this is the Eckart-Young-Mirsky theorem. The operator norm error is ${\sigma }_{k+1}$ for $k<r$. These statements concern specified norms, rather than guaranteeing that discarded details are visually or scientifically unimportant.^[ref]

Consider an $8\times 10$ brightness matrix $B=p{q}^T+a{b}^T/2$, withand $a_i=(-1{)}^{i-1}$, $b_j=(-1{)}^{j-1}$. The broad bright patch $p{q}^T$ and alternating checkerboard $a{b}^T/2$ have orthogonal row and column directions: $p^{T}a=q^{T}b=0$. Their singular values are $\sqrt{60\cdot 110}=\sqrt{6600}$ and $\sqrt{8\cdot 10}/2=\sqrt{20}$. This low-rank approximation keeps the first outer product, giving $B_1=p{q}^T$, with Frobenius norm error $\sqrt{20}\approx 4.472$ and relative error $\sqrt{20/6620}\approx 5.50\%$. For example, $B_{11}=1.5$ becomes $1$, and $B_{12}=1.5$ becomes $2$: every entry changes by $0.5$ in magnitude. The discarded pattern is small but entirely lost.

For this illustrative image compression, storing one normalized left singular vector, one normalized right singular vector, and one singular value requires $8+10+1=19$ scalars instead of $80$. This counts scalars at equal precision, before storage overhead. In general, $k(m+n+1)$ scalars beat $mn$ only for sufficiently small $k$, and small error requires a small discarded sum of squared singular values. The usefulness comes from measuring the tradeoff before throwing information away.^[ref]

A wavelet is a localized analyzing function whose shifted and scaled copies examine a signal at different positions and resolutions. Its usefulness is to separate where a change occurs from how large a region that change spans. A brief feature can contribute to a few nearby wavelet coefficients instead of being described entirely through global oscillations.

The Haar wavelet is the simplest example: compare the first half of an interval with the second. A constant value contributes nothing to this contrast, while a difference between the halves survives. Moving the function changes which part of the signal is examined; shrinking it compares smaller neighbouring regions. In an orthonormal wavelet construction, these comparisons fit together without duplicating squared-norm contributions.

A scaling function retains the coarse information that such contrasts omit. The discrete wavelet transform computes both coarse values and details, and the wavelet series recombines them. This gives signal processing a representation that can expose local structure and support image compression. The transform itself is reversible in the complete orthonormal representation; discarding coefficients introduces approximation error. ^[ref]