Minimization

What are the uses of minimization?

Minimization is useful for finding stable equilibrium, can reformulate systems of equations, and least squares minimizations. We can think of it as a linear system Ax = b, with m equations in n unknowns. We seek to minimize the function $||Ax-b|{|}^2$ where || || refers to norm as seen in Inner Products. .

What is the minimum of p(x)?

The function p(x) has a minimum value of 0, which is only true/works when x is a solution to Ax=b. If there no solution x to the equation, then we find the closest possible solution.

What is least squares solution?

If a linear system has no solution, we look for an approximate solution by minimizing the residual vector: r = b - Ax. We want to minimize the magnitude of the residual $||r||=||Ax-b||$. The value which minimizes the square residual norm function is called the least square solution, denoted $x^{\ast }$.

The least squares solution to Ax = b satisfies: $A^{T}Ax=A^{T}b$ provided that $A^{T}A$ is invertible, the solution is given by: $x^{\ast }=(A^{T}A{)}^{-1}{A}^{T}b$ where:

• A is an m x n matrix
• b is an m x 1 vector
• x is the n x 1 unknown vector

Now, if the measurements have different variances, use a weight matrix C s.t: $A^{T}CAx=A^{T}Cb$ where the solution is: $x^{\ast }=(A^{T}CA{)}^{-1}{A}^{T}Cb$

So, solving a least squares with this formula is as follows:

1. Use the (x, y) points to construct the matrix A and y
2. Compute $A^{T}A$ and $A^{T}y$
3. Solve $A^{T}A[\alpha ,\beta {]}^T=A^{T}y$

What are the flexibilities in LSM?

Least squares solutions depend on the choice of inner product. We can get different solutions depending on the vector space’s inner product. Given a vector b, we seek to find the vector v* which is closest to b in the subspace V. This is equivalent to an orthogonal project of b onto the subspace V. All of this work is equivalent to solving the least squares, minimizing the residual.

What is linear regression?

Linear regression applies least squares to minimize the error of: ${\sum }_{i=1}^n(y_i-{\theta }_0-{\theta }_1{x}_i{)}^2$.

What is gradient descent?

Gradient descent is an iterative optimization algorithm to minimize loss. ${\theta }_{t+1}={\theta }_t-\alpha \Delta J({\theta }_t)$

How does quadratic minimization work?

When finding the minimum for a quadratic equation, we’ve learned how to use calculus. We find where the derivative is equal to zero and that is a minimum. We, then, use the second derivative test to see if the function is concave up, concave down, or unknown.

Consider the multivariate case:

$p(x)=x^{T}Kx-2x^{T}f+c,x\in {\mathbb{R}}^n$

• K: Symmetric n x n matrix
• f: Constant vector
• c: Constant scalar

So if our matrix K is positive definite, then p(x) has a unique minimizer. $x^{\ast }=K^{-1}f$ and our minimum value is: $p(x)=c-f^T{K}^{-1}f$.

So, when we have a multivariate quadratic, turn it into matrix form, and solve for $x^{\ast }$. Then plug them back to get $p(x^{\ast })$.

What are global and local minimum?

A global minimum is a minimum which applies for all inputs to the function. So, you are guaranteed that the most minimum value the function has.

A local minimum is a minimum which exists for a neighborhood of points. It isn’t guaranteed to be the most minimum value of the function.

Going back to our quadratic minimization, if our matrix K is pos. def. then we know there is a unique global minimum at $x^{\ast }$. If it is only positive semi-definite, then the function has multiple global minimum. If K is not pos. semi-definite, then we have no guaranteed global minimum.

What is the closest point problem?

Given a point $b\in {\mathbb{R}}^m$ and a subspace $V\subset {\mathbb{R}}^m$, find the point $v^{\ast }\in W$ that minimizes the Euclidean distance $||v-b||$.

As a projection, the closest point $w^{\ast }$ to b in W coincides with the orthogonal projection of b onto W.

What is a gram matrix?

A Gram Matrix is a symmetric, positive, semi-definite matrix representing the inner products of a set of vectors. So, given the vectors $w_1,w_2,...,w_n$, the Gram matrix K is then: $K_{ij}=⟨w_i,w_j⟩$.

It has the following properties:

• Symmetric: $K_{ij}=K_{ji}$
• Positive Semi-Definite: For any vector x, we have $x^{T}Kx\ge 0$
• Full Rank if Lin Indep: If all the w vectors are independent, K is now positive definite, not just semi-definite

We can use this for the closest point problem: $Kx=f$, where $f_i=⟨w_i,b⟩$. We find the inverse of K where K is the Gram matrix with the entries $K_{ij}=⟨w_i,w_j⟩$ and $f_i=⟨w_i,b⟩$.

If b is in the subspace defined by W, then the closest point is b. This is a useful problem when $b\notin W$.

Minimizing the Squared Distance

What if, instead of minimizing the Euclidean distance, we minimized the squared distance?

$||w-b|{|}^2=⟨w-b,w-b⟩=||w|{|}^2-2⟨w,b⟩+||b|{|}^2$. Well then, plugging in w into that formula, we actually end up with the squared distance formula becoming:

$p(x)=x^{T}Kx-2x^{T}f+c$, where K is the Gram matrix, f is the vector with $f_i=⟨w_i,b⟩$, and $c=||b|{|}^2$.

The quadratic above should look familiar, we can use our quadratic minimization process to find a minimum value to the function.

What are Polynomial Approximation and Interpolation?

We can use least squares fitting into higher degree polynomials. We just use bigger matrices.

We fit a polynomial of degree n: $y(t)={\alpha }_0+{\alpha }_{1}t+...+{\alpha }_n{t}^n$.

The total squared error is minimized: $||e|{|}^2={\sum }_{i=1}^m(y_i-y(t_i){)}^2$

Matrix formulation: $Ax=y$, $$ A = \begin{bmatrix} 1 & t_1 & t_1^2 & \cdots & t_1^n \ \vdots & \vdots & \vdots & \ddots & \vdots \ 1 & t_m & t_m^2 & \cdots & t_m^n \ \end{bmatrix}

If m = n +1, then the Vandermonde matrix is square. The system Ax = y is solvable if A is nonsingular. So if all $t_i$ are distinct, then A is invertible.