← Reference · Nestor G Pestelos Jr · Print this page
Mathematics & Computer Science
Vector (Mathematics and Computing)
A citable reference on vectors: formal vector space axioms, linear independence and bases, inner products, norm metrics, linear transformations, SIMD execution, and high-dimensional representations in machine learning.
See Also & Related References
- 📖 Reference: Vector Search: Approximate Nearest Neighbor (ANN) search, HNSW graphs, and product quantization.
- 📖 Reference: Embeddings: Dense vector representations, semantic manifolds, and continuous metric spaces.
- 📖 Reference: Machine Learning: Empirical risk minimization, feature representations, and generalization theory.
- 📖 Reference: Deep Neural Networks: Multilayer weight matrices, tensor operations, and hidden state activations.
- 📖 Reference: Transformer Architecture: Multi-head attention projections, residual streams, and contextual vector representations.
1. Formal Vector Space Axioms
Vector (in mathematics and computing) is an element of a vector space, represented geometrically as a directed line segment with magnitude and direction, algebraically as an ordered tuple of scalars, or computationally as a contiguous array of numerical data.[1, 2]
1.1 Algebraic Definition
Formally, a vector space (or linear space) over a field \(\mathbb{F}\) (typically the real numbers \(\mathbb{R}\) or complex numbers \(\mathbb{C}\)) is a set \(V\) equipped with two binary operations:
- Vector Addition: \(+: V \times V \to V\), denoted \((u, v) \mapsto u + v\).
- Scalar Multiplication: \(\cdot: \mathbb{F} \times V \to V\), denoted \((a, v) \mapsto a v\).
The set \(V\) must satisfy eight fundamental algebraic axioms for all \(u, v, w \in V\) and all \(a, b \in \mathbb{F}\):[2]
| Category | Axiom Name | Formal Mathematical Statement |
|---|---|---|
| Addition | Associativity | \(u + (v + w) = (u + v) + w\) |
| Commutativity | \(u + v = v + u\) | |
| Identity Element | \(\exists \, 0 \in V \text{ such that } v + 0 = v\) | |
| Inverse Element | \(\forall \, v \in V, \, \exists \, (-v) \in V \text{ such that } v + (-v) = 0\) | |
| Multiplication | Scalar Compatibility | \(a(b v) = (ab)v\) |
| Scalar Identity | \(1 v = v\), where \(1 \in \mathbb{F}\) is the multiplicative identity | |
| Vector Distributivity | \(a(u + v) = a u + a v\) | |
| Scalar Distributivity | \((a + b)v = a v + b v\) |
1.2 Linear Combinations, Span, and Independence
Given vectors \(v_1, v_2, \dots, v_k \in V\) and scalars \(c_1, c_2, \dots, c_k \in \mathbb{F}\), the sum \(w = \sum_{i=1}^k c_i v_i\) is a linear combination. The span of a subset \(S \subseteq V\) is the set of all linear combinations of elements in \(S\):
A set of vectors \(\{v_1, \dots, v_k\}\) is linearly independent if the only scalars satisfying \(\sum_{i=1}^k c_i v_i = 0\) are \(c_1 = c_2 = \dots = c_k = 0\). If non-trivial scalars exist, the set is linearly dependent, meaning at least one vector can be expressed as a linear combination of the remaining vectors.
1.3 Basis, Dimension, and Coordinate Isomorphisms
A subset \(\mathcal{B} = \{e_1, e_2, \dots, e_n\} \subset V\) is a basis of \(V\) if \(\mathcal{B}\) is linearly independent and \(\text{span}(\mathcal{B}) = V\). Every vector \(v \in V\) has a unique expansion in terms of basis \(\mathcal{B}\):
The number of basis vectors \(n\) is an invariant of the vector space, termed the dimension \(\dim(V) = n\). Every finite-dimensional vector space over \(\mathbb{F}\) with dimension \(n\) is linearly isomorphic to the coordinate space \(\mathbb{F}^n\).
2. Inner Product, Normed, and Metric Spaces
Geometric concepts of length, angle, and distance require endowing bare vector spaces with additional algebraic structures.[1, 3]
2.1 Inner Product and Hilbert Spaces
An inner product space is a vector space \(V\) over \(\mathbb{R}\) (or \(\mathbb{C}\)) equipped with an inner product \(\langle \cdot, \cdot \rangle: V \times V \to \mathbb{F}\) satisfying:
- Conjugate Symmetry: \(\langle u, v \rangle = \overline{\langle v, u \rangle}\) (for real spaces, \(\langle u, v \rangle = \langle v, u \rangle\)).
- Linearity in the First Argument: \(\langle a u + b v, w \rangle = a \langle u, w \rangle + b \langle v, w \rangle\).
- Positive-Definiteness: \(\langle v, v \rangle \ge 0\), and \(\langle v, v \rangle = 0 \iff v = 0\).
The Cauchy-Schwarz Inequality bounds the inner product by the product of induced norms:[2]
An inner product space that is complete with respect to its induced metric (every Cauchy sequence converges within the space) is a Hilbert Space \(\mathcal{H}\).
2.2 Vector Norms and Lp Spaces
A norm \(\|\cdot\|: V \to \mathbb{R}_{\ge 0}\) assigns a non-negative scalar length to each vector, satisfying non-negativity (\(\|v\| \ge 0\)), absolute homogeneity (\(\|a v\| = |a| \|v\|\)), and subadditivity (the Triangle Inequality: \(\|u + v\| \le \|u\| + \|v\|\)).
| Norm Family | Mathematical Formula | Geometric Intuition & Properties |
|---|---|---|
| \(L_2\) Norm (Euclidean) | \(\|v\|_2 = \sqrt{\sum_{i=1}^d v_i^2} = \sqrt{\langle v, v \rangle}\) | Straight-line geometric length; strictly convex unit ball; rotationally invariant. |
| \(L_1\) Norm (Manhattan / Taxicab) | \(\|v\|_1 = \sum_{i=1}^d |v_i|\) | Sum of absolute coordinate differences; induces sparse parameter solutions in optimization (Lasso). |
| \(L_\infty\) Norm (Chebyshev / Max) | \(\|v\|_\infty = \max_{1 \le i \le d} |v_i|\) | Maximum coordinate displacement; unit ball is a hypercube. |
| \(L_p\) Norm | \(\|v\|_p = \left( \sum_{i=1}^d |v_i|^p \right)^{1/p}, \quad p \ge 1\) | Generalization across norms; dual norm to \(L_q\) where \(\frac{1}{p} + \frac{1}{q} = 1\) (Hölder's Inequality). |
2.3 Angles and Cosine Similarity
In an inner product space, the angle \(\theta \in [0, \pi]\) between two non-zero vectors \(u, v\) is defined through the Cauchy-Schwarz inequality:
In high-dimensional information retrieval and language modeling, Cosine Similarity measures directional alignment regardless of vector magnitude. Cosine Distance is defined as \(d_{\text{cos}}(u, v) = 1 - \cos(\theta)\).
2.4 Induced Metric Spaces
Every normed vector space induces a metric space \((V, d)\) with distance function \(d(u, v) = \|u - v\|\). Common induced metrics include Euclidean distance \(d_2(u, v) = \sqrt{\sum (u_i - v_i)^2}\), Manhattan distance \(d_1(u, v) = \sum |u_i - v_i|\), and Minkowski distance \(d_p(u, v) = \left(\sum |u_i - v_i|^p\right)^{1/p}\).
3. Vector Operations and Linear Transformations
3.1 Dot, Cross, and Outer Products
- Dot Product (Scalar Product): Maps two vectors \(u, v \in \mathbb{R}^d\) to a scalar \(u \cdot v = u^T v = \sum_{i=1}^d u_i v_i\).
- Cross Product (Vector Product): Defined for \(\mathbb{R}^3\), produces an orthogonal vector with magnitude \(\|u \times v\| = \|u\| \|v\| \sin(\theta)\):
$$u \times v = \begin{bmatrix} u_2 v_3 - u_3 v_2 \\ u_3 v_1 - u_1 v_3 \\ u_1 v_2 - u_2 v_1 \end{bmatrix}$$
- Outer Product (Tensor Product): Produces a rank-1 matrix \(u \otimes v = u v^T \in \mathbb{R}^{m \times n}\) with entries \((u v^T)_{ij} = u_i v_j\).
3.2 Linear Maps and Matrix Representations
A function \(T: V \to W\) between vector spaces is a linear transformation if it preserves vector addition and scalar multiplication: \(T(a u + b v) = a T(u) + b T(v)\). Given ordered bases for \(V\) and \(W\), every linear transformation is uniquely represented by matrix multiplication:
3.3 Orthogonality and Gram-Schmidt Process
Two vectors are orthogonal if \(\langle u, v \rangle = 0\), denoted \(u \perp v\). An orthonormal set satisfies \(\langle u_i, u_j \rangle = \delta_{ij}\) (where \(\delta_{ij}\) is the Kronecker delta).
The Gram-Schmidt Orthogonalization Process converts any linearly independent basis \(\{v_1, \dots, v_k\}\) into an orthonormal basis \(\{u_1, \dots, u_k\}\) by iteratively subtracting vector projections:[1]
3.4 Eigenvectors and Spectral Decomposition
For a linear operator represented by square matrix \(A \in \mathbb{F}^{n \times n}\), a non-zero vector \(v\) is an eigenvector with corresponding eigenvalue \(\lambda\) if:
By the Spectral Theorem, any symmetric real matrix \(A = A^T\) can be factored into an orthonormal basis of eigenvectors: \(A = Q \Lambda Q^T\), where \(Q\) is an orthogonal matrix (\(Q^T Q = I\)) and \(\Lambda\) is diagonal.[3]
4. Computational Representation and Hardware Vectorization
4.1 Memory Layout, Alignment, and Strides
In computer memory, a dense vector \(v \in \mathbb{R}^d\) is represented as a contiguous block of \(d\) IEEE 754 floating-point numbers (e.g. 32-bit float or 64-bit double). Key performance parameters include:
- Stride: The byte offset between consecutive vector elements in memory. A stride of 1 (unit stride) ensures optimal cache line utilization.
- Memory Alignment: Aligning vector starting addresses to 32-byte or 64-byte hardware boundaries allows single-cycle vector load/store instructions without crossing cache line splits.
4.2 SIMD Instruction Sets and Parallel Execution
Modern microprocessors exploit data-level parallelism via SIMD (Single Instruction, Multiple Data) execution units.[4] Rather than executing operations element-by-element in scalar registers, SIMD instructions operate simultaneously on packed vector registers:
- x86-64: AVX2 (256-bit registers, 8 \(\times\) float32 per cycle) and AVX-512 (512-bit registers, 16 \(\times\) float32 per cycle).
- ARM: ARM Neon (128-bit) and Scalable Vector Extension (SVE/SVE2 with variable hardware vector lengths).
- GPUs & TPUs: Massive SIMT (Single Instruction, Multiple Threads) execution across warps (NVIDIA, 32 threads) or wavefronts (AMD, 64 threads), computing matrix-vector products with high memory bandwidth.
4.3 Dense vs. Sparse Vector Encodings
When a high-dimensional vector contains predominantly zero values (for example, bag-of-words text representations or term-frequency indices like BM25), dense storage becomes inefficient:
- Coordinate List (COO): Stores parallel arrays of non-zero indices and scalar values:
indices = [2, 14, 89],values = [0.5, 1.2, -0.8]. - Compressed Sparse Row / Column (CSR / CSC): Compact representation for sparse matrix-vector computations optimizing cache locality and arithmetic throughput.[3]
5. High-Dimensional Vectors in Machine Learning and AI
5.1 Feature Vectors and Coordinate Mapping
In classical machine learning, raw entities (tabular rows, audio signals, pixels) are mapped into a \(d\)-dimensional numerical coordinate space as a feature vector \(x = [x_1, x_2, \dots, x_d]^T \in \mathbb{R}^d\). Supervised decision boundaries (e.g. SVM separating hyperplanes \(w^T x + b = 0\)) operate directly on these geometric representations.[5]
5.2 Latent Representations and Semantic Embeddings
Deep neural networks transform discrete tokens, images, or multimodal artifacts into dense continuous vectors termed embeddings. The internal activations of hidden layers project inputs onto low-dimensional semantic manifolds where geometric distance approximates semantic similarity:
- Word Embeddings (Word2Vec / GloVe): Learned vector spaces capturing linear relational analogies: \(\vec{v}_{\text{King}} - \vec{v}_{\text{Man}} + \vec{v}_{\text{Woman}} \approx \vec{v}_{\text{Queen}}\).[6]
- Transformer Residual Streams: Contextual vectors \(h_t \in \mathbb{R}^{d_{\text{model}}}\) updated sequentially across layers via multi-head self-attention mechanisms.[7]
5.3 Geometric Peculiarities of High Dimensions
As dimensionality \(d\) scales to hundreds or thousands (e.g. \(d = 1536\) or \(d = 4096\)), geometry behaves counter-intuitively due to the Curse of Dimensionality:[5, 8]
- Concentration of Measure: Almost all volume of a \(d\)-dimensional hypersphere of radius \(r\) resides in a thin outer shell of thickness \(\approx r/d\).
- Near-Orthogonality: For independent random vectors uniformly distributed on the unit sphere \(\mathbb{S}^{d-1}\), their inner product concentrates sharply around zero with variance \(\text{Var}(\langle u, v \rangle) = \frac{1}{d}\). Any two random vectors in high dimensions are nearly orthogonal.
- Distance Metric Collapse: The relative contrast between the distance to the nearest neighbor and the distance to the farthest neighbor diminishes:
$$\lim_{d \to \infty} \frac{d_{\max} - d_{\min}}{d_{\min}} \to 0$$
5.4 Vector Indexing and Search
Because exhaustive brute-force \(k\)-Nearest Neighbor search over \(N\) high-dimensional vectors requires \(O(N \cdot d)\) comparisons per query, production retrieval systems rely on Approximate Nearest Neighbor (ANN) indexing:[9]
- Hierarchical Navigable Small World (HNSW): Multi-layer proximity graphs providing \(O(\log N)\) logarithmic search latency.
- Inverted File Index (IVF): Voronoi partitioning of vector space into clusters via \(k\)-means, restricting query searches to adjacent centroids.
- Product Quantization (PQ): Sub-vector decomposition into quantized codebooks, compressing high-dimensional vectors to compact byte codes and enabling fast distance estimation via precomputed lookup tables.
6. References
- ^ Gilbert Strang, Introduction to Linear Algebra, 5th ed. (Wellesley-Cambridge Press, 2016).
- ^ Sheldon Axler, Linear Algebra Done Right, 3rd ed. (Springer, 2015). DOI: 10.1007/978-3-319-11080-6.
- ^ Gene H. Golub and Charles F. Van Loan, Matrix Computations, 4th ed. (Johns Hopkins University Press, 2013).
- ^ John L. Hennessy and David A. Patterson, Computer Architecture: A Quantitative Approach, 6th ed. (Morgan Kaufmann, 2017).
- ^ Christopher M. Bishop, Pattern Recognition and Machine Learning (Springer, 2006).
- ^ Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S. Corrado, and Jeffrey Dean, "Distributed Representations of Words and Phrases and their Compositionality," Advances in Neural Information Processing Systems 26 (NeurIPS 2013). URL: NeurIPS Proceedings.
- ^ Ashish Vaswani, Noam Shazeer, Niki Parmar, et al., "Attention Is All You Need," Advances in Neural Information Processing Systems 30 (NeurIPS 2017). URL: arXiv:1706.03762.
- ^ Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed. (Wiley-Interscience, 2006).
- ^ Yu A. Malkov and D. A. Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs," IEEE Transactions on Pattern Analysis and Machine Intelligence 42(4), 824–836 (2020). DOI: 10.1109/TPAMI.2018.2889473.