3 The Full-Rank Least-Squares Problem

Types: N/A
Examples: N/A
Constructions: 1.4 Two Norms in 2D
Generalizations: N/A

Properties: N/A
Sufficiencies: N/A
Questions: N/A

The Full-Rank Least-Squares Problem

Let $m$ , $n \in N$ with $m \geq n$ . Let $A \in R^{m \times n}$ be a "given" full-rank matrix and $\vec{b} \in R^{m}$ be a given vector. Then, the full-rank least-squares problem is to find all $\vec{x} \in R^{n}$ to minimize the 2-norm of the residual vector:

| | A \cdot \vec{x} - \vec{b} | |_{2}

Just like the 1 The Matrix-Vector Multiplication Problem and the 2A The Nonsingular Linear-Systems Problem, we can describe the full-rank least-squares problem using the function $f : R^{n} \to R^{m}$ with

f (\vec{x}) = A \cdot \vec{x} = \sum_{k = 1}^{n} x_{k} A (:, k)

Based on this definition, we have:

the domain of $f$ is $R^{n}$
the codomain of $f$ is $R^{m}$
the range of $f$ is a subset of $R^{m}$ and most likely not equal to $R^{m}$

The full-rank least-squares problem is a backward problem because we start with the function description (defined my matrix $A$ ) and we are given one specific output value $\vec{b}$ in the CODOMAIN of $f (\vec{x})$ . We are trying to find all possible input values $\vec{x}$ in the domain that produce output value $f (\vec{x})$ "as close as possible" to the vector $\vec{b}$ .

Using the definition of the least-squares problem, we can classify all 2A The Nonsingular Linear-Systems Problem as least-squares problems. For linear systems problems, since $\vec{b}$ begins in the range of $f (\vec{x})$ , we know that

min_{\vec{x} \in R^{n}} | | \vec{b} - A \vec{x} | |_{2} = 0

for each solution. However, not all least-squares problems are linear systems problems. If $\vec{b} \in R^{m}$ with $b \notin Rng (f)$ , we know that $f (\vec{x}) \neq \vec{b}$ for all $\vec{x} \in R^{n}$ . This is the focus of the least-squares problem. Thus, the least-squares problem is a generalization of the linear systems problem that allows us to create "best-fit" approximations to noisy data.