Approximation, Similarity and Representation Methods

Introduction and Context

Data science rarely operates directly on raw objects. Images are represented as pixel arrays, documents as vectors, time series as sequences, and categorical records as embeddings. Once an object has been represented mathematically, we need principled ways to compare it, approximate it, reconstruct it, or transform it into a form suitable for learning. This chapter develops that toolkit.

Approximation concerns replacing a complex object with a simpler one while controlling error. Similarity concerns quantifying how alike two objects are. Representation methods concern the coordinate systems, bases, features, or mappings used to expose useful structure. These ideas support clustering, nearest-neighbour search, dimensionality reduction, signal analysis, feature engineering, interpolation, regression, and nonlinear learning.

The central methodological question is not merely “Which formula should be used?” It is: which geometry and representation make the data-generating structure visible? A distance that is appropriate for physical measurements may be inappropriate for text; a basis that is excellent for smooth signals may be poor for discontinuous ones; and a highly flexible kernel may interpolate training data while generalising poorly.

Learning Objectives

By the end of this chapter, the reader should be able to:

1. Distinguish norms, metrics, similarities, and kernels.
2. Select and interpret distances for numerical, sparse, categorical, and temporal data.
3. Explain basis expansions, Fourier representations, and kernel mappings.
4. Derive and use interpolation and least-squares approximation methods.
5. Analyse approximation error, conditioning, computational cost, and generalisation.
6. Apply these methods to clustering, signal analysis, and nonlinear prediction.

1. Geometry: Norms, Metrics and Similarity

A vector norm measures the size of a vector. For x = (x₁,…,x_d) ∈ ℝ^d, the ℓ_p norm is

The Euclidean norm is ‖x‖₂, the Manhattan norm is ‖x‖₁, and the maximum norm is ‖x‖_∞ = max_j |x_j|. A norm satisfies positivity, homogeneity ‖αx‖ = |α|‖x‖, and the triangle inequality.

A metric is a function d(x,y), defined on a specified domain, satisfying non-negativity, identity of indiscernibles, symmetry, and the triangle inequality. Every norm induces a metric:

The squared Euclidean distance, ‖x−y‖₂², is useful in optimisation but is not itself a metric because it does not generally satisfy the triangle inequality. This distinction matters when interpreting algorithms that assume metric geometry.

1.1 Common data-dependent distances

For observations with positive feature scales s_j, a standardised Euclidean distance is

Here s_j may be a standard deviation or a robust scale estimate. Without scaling, a variable measured in thousands can dominate a variable measured in fractions.

For a positive-definite covariance matrix Σ, the Mahalanobis distance is

It accounts for correlation and unequal variance. Σ must be invertible, or a regularised/pseudoinverse version must be used. Estimating covariance in high dimensions can be unstable; shrinkage estimation is often preferable.

For nonzero vectors, cosine similarity is

It measures orientation rather than magnitude and is particularly useful for term-frequency or embedding vectors. Cosine distance is often defined as 1−sim_cos, but this is not a metric in every unrestricted setting.

Jaccard similarity for finite sets A and B is

It is appropriate for binary presence/absence data when shared zeros should not count as evidence of similarity. For time series, Euclidean distance may be unsuitable when identical patterns occur with temporal shifts; dynamic time warping (DTW) aligns sequences through a constrained warping path, at higher computational cost and with careful attention to boundary and window constraints.

1.2 Similarity, dissimilarity and kernels

A similarity is a high-when-alike score, whereas a dissimilarity is a low-when-alike score. Their numerical scales need not be interchangeable. A positive-semidefinite kernel is a stronger object: for any finite points x₁,…,x_n and coefficients c₁,…,c_n,

Equivalently, the Gram matrix K_ij=K(x_i,x_j) is positive semidefinite. This condition permits a feature map φ into an inner-product space such that K(x,y)=⟨φ(x),φ(y)⟩, even when φ is not explicitly computed.

Important kernels include the linear kernel K(x,y)=x^Ty, polynomial kernel

where γ>0, r is a constant, and integer q≥0, and the radial basis function (RBF) kernel

The RBF bandwidth is often expressed as σ = 1/√(2γ). Large γ produces local, rapidly varying similarities; small γ produces smoother, more global similarities.

2. Approximation as Projection and Compression

Let V be a finite-dimensional subspace of an inner-product space and let f be the target object. The best approximation in the norm induced by the inner product is the orthogonal projection P_V f. It is characterised by

If V=span{φ₁,…,φ_m}, write ĝ=∑_k=1^m a_k φ_k. For observations (x_i,y_i), define the design matrix Φ_ik=φ_k(x_i). Least squares chooses a to minimise

The normal equations are

If the columns of Φ are linearly independent, the solution is unique. In numerical practice, QR or singular-value decomposition is preferred to explicitly forming (Φ^TΦ)^-1, because normal equations square the condition number.

The residual decomposition illustrates the projection principle. If ĝ is the orthogonal projection, then f−ĝ is orthogonal to every candidate direction in V, so no other element of V has smaller squared error.

2.1 Basis expansions and feature engineering

A basis expansion represents a scalar input through features such as

Polynomial bases use φ_k(x)=x^k, but high-degree monomials can be badly conditioned. Legendre, Chebyshev, spline, wavelet, and Fourier bases are often numerically or structurally superior. A basis should reflect expected regularity: splines provide local control, Fourier functions represent periodicity, and wavelets provide localisation in both scale and position.

For multivariate data, tensor-product bases can grow exponentially with dimension. This is the curse of dimensionality. Alternatives include additive models, low-rank decompositions, random features, sparse bases, and learned representations.

3. Fourier Methods for Signals and Features

For a continuous periodic function with period T, the Fourier series is

Under standard integrability conditions, the coefficients are

The series separates a signal into frequencies. For sampled data x₀,…,x_N−1, the discrete Fourier transform (DFT) is

The inverse transform is

where i=√(−1). The fast Fourier transform computes the DFT in approximately O(N log N) operations rather than O(N²).

The sampling interval ∆t gives sampling frequency f_s=1/∆t. Frequencies above the Nyquist frequency f_s/2 cannot be uniquely recovered from uniformly sampled data and may alias into lower frequencies. Anti-aliasing low-pass filtering before sampling is therefore essential.

Fourier features can be used in regression, anomaly detection, seasonality modelling, and neural networks. Windowing reduces spectral leakage caused by analysing a finite segment, but changes amplitude and frequency resolution. A spectrogram applies a short-time Fourier transform over overlapping windows, trading temporal resolution against frequency resolution.

4. Interpolation and Function Approximation

Interpolation constructs a function that matches specified values exactly. Given distinct nodes x₀,…,x_n and values y₀,…,y_n, the Lagrange polynomial is

It satisfies p(x_j)=y_j. For a sufficiently smooth function, the interpolation remainder is

for some ξ in the interval containing the nodes and x. The formula explains why error depends on both function smoothness and node placement. Equally spaced high-degree interpolation can exhibit Runge oscillations near boundaries. Chebyshev nodes reduce the worst-case polynomial interpolation error.

Piecewise cubic splines avoid the instability of a single high-degree polynomial. A natural cubic spline is twice continuously differentiable and has zero second derivative at the endpoints. Splines are valuable in data science because they combine smoothness with local modification: changing one observation affects nearby intervals rather than the entire domain.

Interpolation is exact fitting and therefore can be dangerous with noisy measurements. Smoothing splines instead minimise

where λ≥0 controls the trade-off between fidelity and smoothness. At λ=0, the method approaches interpolation; increasing λ penalises curvature more strongly. The integral assumes a one-dimensional function with a square-integrable second derivative.

5. Kernel Approximation and Nonlinear Learning

Kernel methods replace explicit coordinates with pairwise evaluations. In kernel ridge regression, predictions take the form

and the coefficient vector solves

where K is the Gram matrix, λ>0 is a regularisation parameter, I is the identity matrix, and y is the response vector. Regularisation improves conditioning and limits overfitting. Exact computation requires storage and factorisation costs that grow approximately quadratically and cubically with sample size, respectively; approximation methods such as Nyström sampling and random Fourier features address this limitation.

The representer principle explains why many regularised problems have finite expansions over training points. For a loss depending on training predictions and a penalty based on the reproducing-kernel Hilbert-space norm, an optimum lies in the span of K(x_i,·). This converts an infinite-dimensional optimisation problem into one involving n coefficients.

Random Fourier features approximate shift-invariant kernels. For a suitable spectral distribution, one constructs a finite map z(x) such that z(x)^Tz(y)≈K(x,y). A linear model on z(x) then approximates a kernel model at lower computational cost, with approximation accuracy depending on the number of random features.

6. Worked Example: Choosing a Similarity Geometry

Suppose two documents are represented by term-frequency vectors x=(3,0,1) and y=(6,0,2). Their Euclidean distance is

Thus Euclidean distance regards the documents as different in magnitude. Their cosine similarity is

They have identical direction and therefore identical relative term composition. For document retrieval, cosine similarity may be more meaningful because document length should not alone determine topical similarity. This conclusion depends on the representation: if absolute document volume is substantively important, Euclidean or count-based models may be preferable.

7. Applied Case: Predictive Maintenance from Vibration Signals

Background

This illustrative case concerns a manufacturer monitoring rotating machinery. Each machine produces a vibration signal sampled at a fixed frequency, together with operating temperature, load, and maintenance history.

Problem

The organisation wants to detect bearing degradation early while avoiding false alarms caused by changes in machine load. Raw signals have different lengths and amplitudes, and labelled failures are scarce.

Analysis

First, signals are synchronised and converted to comparable units. A windowed Fourier transform produces spectral-energy features in physically meaningful frequency bands. Each feature is standardised using training-set statistics only. Similar machines are grouped using a distance that accounts for feature covariance, while cosine similarity is used for selected normalised spectral profiles.

For prediction, an RBF-kernel classifier is trained with nested cross-validation. The kernel width and regularisation are selected inside the training folds, preventing information leakage. Because failures are rare, evaluation reports precision, recall, false-alarm rate, and time-to-warning rather than accuracy alone.

Approach and outcome

The resulting system combines interpretable band-energy features with a nonlinear decision boundary. A held-out temporal test set is used to assess deployment performance. Thresholds are chosen with maintenance costs in mind: a missed failure may be much more expensive than an inspection. The system also reports uncertainty or abstains when the signal lies far outside the training distribution.

Learning points

Representation choices determine the problem geometry. Windowing and anti-aliasing affect the validity of spectral features. Scaling and covariance estimation affect clustering. Kernel parameters control locality and must be tuned without test-set contamination. Finally, a technically accurate detector is not operationally successful unless alarms are actionable and monitored for distribution shift.

8. Limitations, Governance and Best Practice

Approximation introduces bias, while excessive flexibility increases variance. The approximation–estimation–noise decomposition is conceptual rather than a universal exact identity, but it clarifies why a richer basis does not automatically improve prediction. Cross-validation, regularisation, and a genuinely untouched test set are central safeguards.

Distance measures can encode social or institutional assumptions. For example, a similarity model used in hiring, credit, or healthcare may reproduce historical inequities if its features or labels reflect unequal treatment. Sensitive attributes should not be casually removed: proxies may remain, and fairness analysis may require retaining them for auditing. Data minimisation, access control, explainability, and documentation of feature construction are important governance practices.

Best practice includes: inspect distributions and units; scale using training data; test sensitivity to metric and kernel choices; use stable numerical decompositions; diagnose conditioning; tune hyperparameters within resampling folds; monitor drift; preserve provenance of transformations; and report computational cost alongside predictive performance. Approximation quality should be evaluated in the task-relevant loss, not only by a generic reconstruction error.

Contemporary Directions

Modern representation learning often learns embeddings rather than specifying all features manually. Contrastive learning explicitly shapes embedding geometry through positive and negative examples, while neural operators and Fourier neural operators use spectral representations for function-valued data. Approximate nearest-neighbour systems use compressed or quantised embeddings to scale similarity search. These developments do not eliminate classical mathematics: norms, kernels, bases, sampling theory, and regularisation remain essential for interpreting, validating, and governing learned representations.

Chapter Summary

Norms define size and induce distances; metrics formalise comparison, while similarities quantify affinity. Feature scaling, covariance structure, sparsity, set membership, and temporal alignment determine which comparison is appropriate. Basis expansions approximate functions in finite-dimensional spaces, with orthogonal projection and least squares providing fundamental solutions. Fourier methods expose frequency structure but require attention to sampling, aliasing, leakage, and resolution. Interpolation fits specified values exactly, whereas splines and smoothing penalties control instability and noise. Positive-semidefinite kernels provide implicit nonlinear representations and lead to kernel ridge regression, support-vector methods, and scalable approximations. Across all methods, geometry, conditioning, regularisation, validation, computational cost, and governance must be considered together.

Key Terms

Norm: A function measuring vector magnitude and satisfying positivity, homogeneity, and the triangle inequality.

Metric: A distance function satisfying non-negativity, identity, symmetry, and the triangle inequality.

Cosine similarity: The inner product of two nonzero vectors after normalising their lengths.

Mahalanobis distance: A covariance-adjusted distance between observations.

Kernel: A function representing an inner product in an explicit or implicit feature space.

Gram matrix: The matrix of pairwise kernel evaluations.

Positive semidefinite: A matrix or kernel whose quadratic form is nonnegative.

Basis expansion: Representation of a function as a weighted sum of basis functions.

Orthogonal projection: The closest element of a subspace under an inner-product norm.

Least squares: Estimation by minimising the sum of squared residuals.

Conditioning: Sensitivity of a numerical problem to perturbations in input data.

Fourier series: Expansion of a periodic function into sinusoidal components.

DFT: Discrete Fourier transform of a finite sampled sequence.

Aliasing: Misrepresentation of high frequencies as lower frequencies after sampling.

Interpolation: Construction of a function matching given data values exactly.

Spline: A piecewise polynomial joined with specified smoothness conditions.

Regularisation: A penalty or constraint used to control complexity and instability.

RBF kernel: A Gaussian-shaped kernel based on squared Euclidean distance.

Representer principle: Result stating that many regularised kernel solutions lie in the span of training-point kernels.

Approximation error: Discrepancy caused by restricting a target to a simpler representation class.

Review Questions

Short Answer Questions

1. What distinguishes a norm-induced metric from squared Euclidean distance?
2. Why is feature scaling important when computing Euclidean distances?
3. State the positive-semidefinite condition for a kernel Gram matrix.
4. What is aliasing, and how can it be reduced?
5. Distinguish interpolation from smoothing-spline approximation.

Long Answer Questions

1. Compare Euclidean, cosine, Mahalanobis, and Jaccard measures, including suitable data contexts and limitations.
2. Explain least-squares projection using a basis matrix and discuss why QR or SVD is numerically preferable to normal equations.
3. Derive the role of sampling frequency and Nyquist frequency in discrete Fourier analysis.
4. Explain how kernel ridge regression produces nonlinear predictors and why regularisation is necessary.
5. Discuss the curse of dimensionality in basis expansions and evaluate strategies for controlling it.

Analytical / Application Questions

1. A clustering project combines income, age, and transaction counts measured on very different scales. Design a defensible distance-based preprocessing and validation procedure.
2. A sensor is sampled at 800 Hz. Determine the highest frequency that can theoretically be represented without aliasing and propose a preprocessing pipeline for a 300 Hz signal component.
3. A document system must decide whether topic similarity should ignore document length. Compare cosine and Euclidean geometry using a mathematical argument and recommend an evaluation design.

Multiple Choice Questions with Answers

Question 1

Which property is required of a metric but not necessarily of squared Euclidean distance?

A. Symmetry

B. Non-negativity

C. Triangle inequality

D. Identity of indiscernibles

Correct Answer: C. Triangle inequality

Question 2

For nonzero vectors, cosine similarity primarily measures which aspect?

A. Absolute magnitude

B. Orientation

C. Covariance estimation error

D. Temporal alignment

Correct Answer: B. Orientation

Question 3

In the Mahalanobis distance, what does the covariance matrix account for?

A. Class labels only

B. Feature correlation and unequal variance

C. Fourier phase only

D. Missing values automatically

Correct Answer: B. Feature correlation and unequal variance

Question 4

If a signal is sampled at 800 Hz, its Nyquist frequency is:

A. 200 Hz

B. 400 Hz

C. 800 Hz

D. 1600 Hz

Correct Answer: B. 400 Hz

Question 5

What is the principal computational advantage of the fast Fourier transform over a direct DFT?

A. It removes the need for sampling

B. It changes a real signal into a categorical variable

C. It reduces typical complexity from O(N²) to approximately O(N log N)

D. It guarantees no spectral leakage

Correct Answer: C. It reduces typical complexity from O(N²) to approximately O(N log N)

Question 6

In least-squares approximation, the residual from an orthogonal projection is:

A. Parallel to every basis vector

B. Orthogonal to the approximation subspace

C. Always zero

D. Independent of the basis

Correct Answer: B. Orthogonal to the approximation subspace

Question 7

Which kernel is defined by exp(−γ‖x−y‖²) with γ greater than zero?

A. Linear kernel

B. Polynomial kernel

C. RBF kernel

D. Jaccard kernel

Correct Answer: C. RBF kernel

Question 8

What is a principal risk of high-degree polynomial interpolation on equally spaced nodes?

A. It cannot match any data values

B. Runge-type boundary oscillations

C. It always produces a constant function

D. It eliminates measurement noise

Correct Answer: B. Runge-type boundary oscillations

Question 9

In kernel ridge regression, the term λI primarily provides:

A. Regularisation and improved conditioning

B. A guaranteed zero training error

C. Temporal alignment

D. Antialiasing

Correct Answer: A. Regularisation and improved conditioning

Question 10

For x=(3,0,1) and y=(6,0,2), their cosine similarity is:

A. 0

B. 0.5

C. 1

D. √10

Correct Answer: C. 1