Application of LS to Time Series Analysis

Predicting the future based on the past few steps. If we have the weights and if we have the previous positions, can predict next steps. Assuming the error term is zero mean. e(k) = y(k) - wTphi(k)

problem how to learn the weights w. How should i go about learning them?

Idea: sample. training data. Formulate an optimization problem. given training data, how to estimate the weights.

Problem:

mine - what are $\varphi$ vectors? Suppose we observed the past history y(1), y(2), ... y(N). This is the same as observing $\varphi (1),\dots \varphi (N)$

IDEA: $y(k)\sim w^T\varphi (k)$

Formulate as LS problem: minimize $\Vert \varphi w-y\Vert$. phi is a matrix with phi(1)^T … phi(N)^T as rows. check picture.

y = y vector column

Note that all we need is linear in w. y(k) can be “not” linear.

Question: what if y(k) is a quadratic function of previous y(k-1) , y(k-1)?

$y(k)=w_{1}y(k-1)+w_2(k-2)+w_{3}y(k-1)y(k-2)+w_{4}y(k-1{)}^2+w_{5}y(k-2{)}^2+e(k)$

The same scheme works for $\varphi (k)$

---

Linear equations in Engineering. (Friendly Review of Some Examples)

Utility and modeling everything. the focus of 16A. Applied linear algebra. Modelling in real life (engineering sense)

Will become useful later for modeling things. reduce optimization models and so forth.

• Good for modeling constraints in Engineering / Science. A lot of things in natural are linear.

Example 1: Tomography (16A) key- take log to make the equations linear

Example 2: Network Flows (Direct Graphs)

Linear Algebra’s Role

Linear algebra provides the tools to model and solve these problems. Here’s how:

1. Variables: We use variables to represent the flow through each part of the network (e.g., the amount of water in a pipe, the number of cars on a road).

2. Equations: The key principle is conservation of flow:

   • Conservation of flow : The total flow into the network must equal the total flow out.
   • Feasible Flow : At any intersection (node), the flow in must equal the flow out. ${\sum }_{e\in incoming}{x}_e={\sum }_{e\in outgoing}{x}_e$ ${\sum }_{u\in Vst(u,v)\in E}{x}_{(u,v)}={\sum }_{e\in outgoing}{x}_e$

1 & 3 & 4 & \end{matrix}$$

These principles translate into a system of linear equations.

3. Matrices: We represent the network and the flow equations using matrices. This allows us to use efficient techniques like Gaussian elimination to solve for the unknown flows.

---

Linear equations in optimization

minimize f(x) over x such that $Ax=b$ (Transporting Corn Example, Network Flow)

$mi{n}_{x}f(x)$

Review of Linear Algebra Module. Big Points. What are important according to Tom.

• Linear Algebra = Language of Optimization
• Basic Object: vectors, matrices.
• Important Concepts: Subspaces, Bases, Norms, Inner Products, etc.
  • Fundamentally Geometric in Nature.
• Some of the most important Tools:

  • Projection (everything of this course {in a sense})

    • Given Subspace S, solve ${\pi }_s(x)=argmi{n}_{x\in S}|s-x{|}^2$
    • Solution characterized by Orthogonality
      • Meaning $x-{\pi }_s(x)$ and $y$ are orthogonal. $(x-{\pi }_s(x){)}^{T}y=0\forall y\in S$
    • IMPORTANT: Projection is a linear transformation $x\to {\pi }_s(x)$
    • Applications:
      • Gram-Schmidt (Sequential Projection) Input = $x_1\dots x_n$ and Output $u_1\dots u_n$ Application of Gram-Schmidt → QR Decomposition

  • Matrices represent Linear Transformation

    • Four Fundamental Subspaces (The picture)
    • Pseudo-Inverse
    • The picture can sometimes can allow us to better understand / reduce problems.
      • One good example: $mi{n}_x|Ax-b{|}^2\text{such that}Cx=d$ transform to $mi{n}_z|A{x}_0+A{N}_z-b{|}^2\text{where}{x}_0=C^{+}d$
      • Basically transform an optimization problem with linear constraint to a least square problem.

  • Many of the other concepts we saw from optimization problems:

    • Example if A is a symmetric n x n matrix, ${\lambda }_{max}(A)=ma{x}_x\frac{x^{T}Ax}{x^{T}x}$
    • Repeat to get Spectral Decomposition = $A=U\Lambda U^T=\sum {\lambda }_i{u}_i{u}_i^T$
    • Applications: PCA : just take spectral decomposition of $X{X}^T$

  • Singular Value Decomposition $A=U\Sigma V^T$ Comes from an optimization problem

    • For Generic $A\in R^{m\times n}$
      • $v_1=argma{x}_{v:|v|=1}|Av{|}_2$
      • ${\sigma }_1=|A{v}_1{|}_2$
      • $u_1=\frac{A{v}_1}{{\sigma }_1}$
    • Application:
      • Low Rank Approximation
      • PseudoInverse $A^{+}=V{\Sigma }^{+}{U}^T$ Solving Least Squares, Mapping between Subspaces.