Vector Norms¶
Formula¶
\[
\|x\|_p = \left(\sum_i |x_i|^p\right)^{1/p}\quad (p\ge 1),\qquad \|x\|_\infty = \max_i |x_i|
\]
Parameters¶
- \(x\): vector
- \(p\): norm order
What it means¶
Measures vector size with different emphasis on components.
What it's used for¶
- Measuring vector/matrix size.
- Regularization (L1/L2) and stability.
Key properties¶
- \(\|x\|_2\) is Euclidean length
- Norms are homogeneous and satisfy triangle inequality
Common gotchas¶
- \(\|x\|_0\) is not a norm (counts nonzeros).
- Different norms can change optimization geometry.
Example¶
For \(x=(3,4)\), \(\|x\|_2=5\), \(\|x\|_1=7\), \(\|x\|_\infty=4\).
How to Compute (Pseudocode)¶
Input: vector x and norm type (for example, p-norm or infinity norm)
Output: ||x||
if p-norm:
s <- sum_i |x[i]|^p
return s^(1/p)
if infinity norm:
return max_i |x[i]|
Complexity¶
- Time: \(O(n)\) for a vector of length \(n\)
- Space: \(O(1)\) extra space
- Assumptions: Vector norms shown; matrix norms can require different computations and higher cost