Undersampled least squares solution in FunctionalChaosAlgorithm


I construct a PCE model using
algo = ot.FunctionalChaosAlgorithm(train_in, train_out, jpdf, adaptiveStrategy, projectionStrategy),
projectionStrategy = ot.LeastSquaresStrategy()
adaptiveStrategy = ot.FixedStrategy(multivariateBasis, enumerateFunction.getStrataCumulatedCardinal(p)).

Having 9 input parameters and p=3, the PCE basis consists of 220 polynomials. For a training data set of size 100 or 200, I get a solution (an inaccurate one, but still a solution), which should not be the case if the standard normal equations or QR decomposition solution methods are used for the least squares minimization, since the least squares system is underdetermined.

So, my question is, what kind of algorithm is used “under the hood” to compute the least squares solution? Is it some kind of optimization algorithm? If yes, which one?


Hi Dimitris,

In the under determinate case, the least-squares solution is the solution of minimal norm among all the possible solutions, in the sense of the dgelsy LAPACK routine (https://linux.die.net/man/l/dgelsy. It makes sense here as we are using an orthogonal basis.

You can monitor which algorithm is used by adding ot.Log.Show(ot.Log.INFO). You will get these two lines in the log flow:

INF - Run the approximation algorithm
INF - In PenalizedLeastSquaresAlgorithm::run(), use QR decomposition