1
$\begingroup$

Could someone please point me to an understandable definition of the Kolmogorov n-width? I'm having a hard time figuring out what is the output of the definition - is it an integer?

Edit: I realize that my question was not well-posed. This paper defines the Kolmogorov n-width as

$$ d_n(\mathcal{M})= \inf_{\mathcal S_n} \sup_{f\in\mathcal{M}}\inf_{g\in\mathcal{S_n}} \|f-g\| $$ where, the first infimum is taken over all n-dimensional subspaces of the state space, and $\mathcal{M}$ denotes the manifold of solutions over all time and parameters.

Does this mean that the Kolmogorov n-width is the minimum over all n-dimensional subspaces of the state space of width $n$, of the maximum of the minimum error between all $f\in\mathcal{M}$ and all $g\in\mathcal{S_n}$.?

How does this definition (and my understanding) relate to the nice and detailed explanation given by @DavidePapaPicco below?.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Given the tags of your question I believe you are refererring to the rate of decay of the singular values of a SVD performed on a snapshot matrix of a full-order model.

The general (not exhaustive) setup is that, given the snapshot matrix $ \boldsymbol{\mathcal{X}}\in\mathbb{R}^{N_R\times N_C}$, then the SVD would give you the left $\boldsymbol{L}$ and right $\boldsymbol{R}$ singular vector matrices whose columns span the low-rank manifold of the reduced order solution alongside the (diagonal) singular values matrix $\boldsymbol{\Lambda}$ $$ \boldsymbol{\mathcal{X}}\approx\boldsymbol{L}\boldsymbol{\Lambda}\boldsymbol{R}\;,\quad\boldsymbol{\Lambda}\in\mathbb{R}^{N_R\times N_R} $$ If you truncate the list of singular values in diag(Lambda) to the first $R<N_R$ terms then the reduced order model given by the $R-$dimensional low rank space spanned by the corresponding $R$ singular vectors, would carry an approximation error generated by the truncatation with respect to the full order model.

If you set a (arbitrary) treshold of accuracy for such error (say 1% of the accuracy retained by the reduced order model) than the Kolmogorov n-width is the minimum value of $R$ (i.e. number of singular vectors) required by the ROM to retain the truncation error below such treshold.

Suppose you have you are given X as the snapshot matrix and e as the aforementioned accuracy treshold, then the implementation of the Kolmogorov n-width would be R = kolmogorov(X,e).

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thank you very much. This is very nice and useful. It never occurred to me to think like this about the Kolmogorov n-width; I was thinking in terms of the definition given in the paper now mentioned in my question. I should have been more clear; but I thought the definition of the Kolmogorov n-width given in the paper was the one that everyone uses. $\endgroup$
    – NNN
    Commented Nov 11, 2022 at 5:35
  • $\begingroup$ I think the connection between what you wrote and the inf-sup-inf condition that I wrote is that the optimal projector of given rank (dimension) can be constructed through the SVD. $\endgroup$
    – NNN
    Commented Nov 11, 2022 at 14:41
  • 1
    $\begingroup$ The first infimum is taken over all the subspaces (of dimension n) of the solution manifold as you correctly pointed out. Then you take the sup of all the solution in the FOM so that you consider "the worst case scenario" as in of all the solutions in the FOM consider that with the highest energy (in terms of dynamical systems) and then subrtract it pointwise (i.e. for each entry in your vector of function values) from the infimum of low-rank solutions. The output will thus be the minimum number (first inf) of low-rank dimensions n that makes g "as close as possible" to f. $\endgroup$
    – Davide Papapicco
    Commented Nov 14, 2022 at 12:30
  • $\begingroup$ The term "as close as possible" is quantified by the error treshold I mentioned in the answer. A definition of such quantity can be found on page 2, eq. (2), on this pre-print (arxiv.org/pdf/2108.06558.pdf). I did cite myself because it was the quickest reference I could think of but there is a ton of further literature out there that is perhaps more explanatory than that. $\endgroup$
    – Davide Papapicco
    Commented Nov 14, 2022 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.