SVD and Its Application to Dynamical Systems

Instructions on the structure of the term project and uploading requirements

Instructions on the structure of the term project and uploading requirements:

• Discussion below explains the required concepts in detail. Throughout the text, several problems are listed that you need to answer. However, your term project submission should be a coherent report. Therefore do NOT simply answer the problems. Follow the pattern of the document below. Do not use the text verbatim; shorten and explain things in your own sentences. Then, when you reach a certain problem, such as Problem 1.1, 1.2 etc, include its answer in the corresponding location and continue your discussion. Your criterion should be that your term project needs to be a coherent, well-written report; rather than a collection of solutions to specific problems.

• You are required to type your term project using your favorite editing software. Hand-written solutions are not acceptable. Term projects that do not o↵er a coherent discussion (i.e., simply lists solutions to the specific problems as in a homework assignment) will loose at least 20%.

• Students must submit their solutions electronically as a pdf upload to the course Canvas site.

• The entire assignment must be submitted as ONE pdf file.

• The Matlab scripts need to be attached to the pdf file. Include the code after the corresponding question. Also, the plots should be included in the pdf file, once again in the answer of the corre- sponding problem; not in the end. Do not simply attach a screen shot of the scripts. We will run these scripts if needed. We should be able to copy-paste the code to run.

• For those who are using LaTeX: The mcode package is great for including MATLAB code in LaTeX. The graphicx package can be used to include images in LaTeX.

• Submitted documents must answer questions in order. If you do not answer a question or part of a
question, please indicate this on your assignment.

 The SVD and Learning Dynamical Systems from Data

In Section 1, we have studied SVD and its power in producing optimal low-rank approximations. Given a matrix A (representing an image, or a database of images), we used its SVD to compute its low-rank approximation. In this section, we will use SVD to learn a discrete-time dynamical system from its time-domain data. Thus, we will not be given the matrix A; rather we will be given time-domain simulation data from a dynamical system and use SVD to construct the underlying transition matrix A.

Data-Driven Learning of Dynamical Systems

Consider the following discrete-time linear dynamical system:

x(k + 1) = Ax(tk), x(0) = x0, for k = 0, 1, 2, . . . , (2.1)where x(k), x0 2 Rn and A 2 Rn?n. Unlike our analysis in the class, here we do not have access to A;i.e., we do not know the underlying transition matrix. However, we have access to measurements of the state x(t), i.e., we have the measurements/observations x(0), x(1), x(2), x(3), · · · , x(N ) where N is the final time. This is a common occurrence in practice. For example, recall Problem 1 of Homework 1 (and Homework 3) where we modeled the voting preference in a city. We were able to do this since we were explicitly specified how voter preference varies from one year to the next. However, in practice, we will not have explicit access to this information; in other words, to A.

Instead, after every year (or every election), through surveys, exit polls, we have a huge data showing how people have voted. Therefore, we have the measurements:

 x(0), x(1), x(2), · · · , x(N ) , X = ?x(0) x(1) x(2) · · · x(N )? 2 Rn?(N +1)

Now, given this data (2.2)(called measurements or state history), our goal is to find the state-transition matrix A, that has produced this data. In other words, our goal is find the underlying model (the state transition matrix A) that produced this data.

 Setting up the optimization problem to learn A

Let us formulate this data-driven learning problem formally. If we were to find the transition matrix A exactly, it should satisfy:

x(1) = Ax(0), , x(2) = Ax(1), x(3) = Ax(2), · · · x(N ) = Ax(N)

Algorithm 2.1 is at the core of the Dynamic Mode Decomposition method for fitting a linear dynamical system to a given data set. It has a wide spectrum of applications ranging from flow control to neuroscience and many others; you may check [2] and references therein for more details. First, we will apply this algorithm to a synthetic data.