9
$\begingroup$

I have a linear ordinary differential equation (ODE) with a system matrix with constant coefficients: $$\dot{y}(t) = \mathcal{A}\; y(t), \quad y(0) = y_0$$ with $y(t) \in \mathbb{R}^{n \times 1}$ and $\mathcal{A} \in \mathbb{R}^{n \times n}$ where $\mathcal{A}$ has constant coefficients. I have a (large) series of $r$ (with $r \gg n^2$) datapoints $y_{i}$ for time points $t_i$ (including $y_0$ for $t=t_0$). The elements of the matrix $\mathcal{A}$ are unknown and I'm interested in estimating these.

In general, this is considered as an inverse problem. Is there a more specific terminology for this example (constant coefficients, linear ODE, system matrix identifcation)?

What are the current techniques to solve this type of problem? How sensitive is the problem to noisy data?

My "brute force" approach would be

  1. Write the elements of matrix $\mathcal{A}$ in a vector $a = [a_{11}, a_{12}, \ldots, a_{1n}, a_{21}, \ldots, a_{2n}, \ldots, a_{nn}]$
  2. Write down the equations for each $t_i$ time point using some approximation for $\dot{y}(t) \approx \frac{y_{i} - y_{i-1}}{\Delta t}$
  3. Build a linear least squares problem using this systems matrix and the vector of unknowns.
  4. I can perform an SVD decomposition $\mathcal{A} = U\Sigma V^{t}$
  5. Since the problem is homogeneous, the LS optimum would be the last column of $V$.

But the problem is of course, that if the number of data points gets larger, the computation of the full SVD becomes memory and time consuming.

Given the simplicity of the problem formulation (leading to a very structured matrix $\mathcal{A}$), I would be surprised if there is no specific, more optimal, method developed for this type of problem. Would an approach with the formal solution using the matrix exponential $y(t) = e^{\mathcal{A}t}y_{0}$ lead to a more optimal algorithm?

$\endgroup$
  • 5
    $\begingroup$ In frequency domain this is $Y(i\omega) = (i\omega I -A)^{-1}Y(0)$. In control theory circles this is called system identification. $\endgroup$ – percusse Nov 22 '17 at 11:54
  • 2
    $\begingroup$ Note that you want $r > n^{2}$, not just $n$ because there are $n^{2}$ parameters to identify. $\endgroup$ – Brian Borchers Nov 22 '17 at 12:37
  • 5
    $\begingroup$ Note that this is not a linear inverse problem even if the ODE is linear, since the mapping $a\mapsto y$ is not. (This also means that $r>n^2$ is in general neither necessary nor sufficent.) Another keyword would be "output least squares" (a.k.a. Tikhonov regularization) together with "adjoint approach". $\endgroup$ – Christian Clason Nov 22 '17 at 13:22
  • $\begingroup$ As @percusse already mentioned, this is (a simple case of) linear black-box system identification, about which there are of course dozens of textbooks available. You might be interested in, e.g. chapter 7 of the book of Söderström and Stoica: user.it.uu.se/%7Ets/sysidbook.pdf. $\endgroup$ – jhin Feb 5 at 19:32
  • $\begingroup$ On another note, where does the "very structured matrix A" come from? I see no corresponding assumption being made above? If you assume some specific strucure (e.g. a particular transfer function model --> see the Söderström/Stoica book again), the identification problem becomes of course much easier. $\endgroup$ – jhin Feb 5 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.