-
Notifications
You must be signed in to change notification settings - Fork 3
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
"LU matrix is singular" Error for well-behaving data (LuDecomposition.solve in ml-matrix) #10
Comments
Hi @saunus and sorry about that. I don't have Matlab installed, but does this result look correct ? (At least the last term is negative) PolynomialRegression {
degree: 2,
powers: [ 0, 1, 2 ],
coefficients: [
0.0004257708983743669,
0.08609266575876973,
-0.00021019886491302486
]
} Also I have tested old and newer versions of the software, and I think we just need to pass (The mathematical reason could be that by rounding errors those rows end up being multiple of each other, that would make the system of equations unsolvable without SVD, probably.) So I may send a PR with this fix. |
I'd assume this is left in user's hands at least for now, since it would require quite a few changes. Maybe @targos has a different idea, otherwise we may update the docs and close the issue. |
I've been doing some research on this issue, and it seems to be that calculating I have replaced it by a QR decomposition, and got this results:
Which although they are in a different order, are very close to what is reported:
I could try to find some backing for the claim, if there is will to change (only a few lines) of the algorithm. Basically, now it does not use the transpose but does this: const qrF = new QrDecomposition(F);
console.log(qrF, F, y);//temporary
return {
coefficients: qrF.isFullRank()
? qrF.solve(Y).to1DArray()
: solve(F, Y).to1DArray(),
degree: Math.max(...powers),
powers,
}; So at least seems to extend the range of usability. Currently all tests pass but one. |
Hi, I did not dare to ask for QRDecomposition in first place:
But maybe something to give you confidence: QR-decomposition is used by matlab internally for least-squares: function [p,S,mu] = polyfit(x,y,n)
% Construct the Vandermonde matrix V = [x.^n ... x.^2 x ones(size(x))]
V(:,n+1) = ones(length(x),1,class(x));
for j = n:-1:1
V(:,j) = x.*V(:,j+1);
end
% Solve least squares problem p = V\y to get polynomial coefficients p.
[p, rankV, QRfactor, perm] = matlab.internal.math.leastSquaresFit(V,y1); where leastSquaresFit is function [p, rankV, QRfactor, perm] = leastSquaresFit(V,y)
% Solve least squares problem p = V\y to get polynomial coefficients p.
[QRfactor, tau, perm, rankV, ~] = matlab.internal.decomposition.builtin.qrFactor(V, -2);
% use nonzero diagonal entries to determine rank for qrSolve.
rV = sum(abs(getDiag(QRfactor)) ~= 0);
% QR solve with rank = rV.
p = matlab.internal.decomposition.builtin.qrSolve(QRfactor, tau, perm, y, rV); I can not contribute, on what downside the change to QRDecomposition might have. But I would definitely appreciate to have the option to use it in this package. Thanks for your help |
It makes sense. I think one approach could be to either do it when it fails, and do QR as a fallback, and another one would be use QR first. I will try the second approach for now, and will add a benchmark to see how bad it gets. For the moment, the results seem better (but I think it does not get so close as the results you shared.)
It will take a little while though, cause I don't want to introduce a more complex approach that we can't fix later on. Any extra data (just the arrays of numbers.) where it fails would be great. |
Hi, I extracted a full data set of 450 curves to fit: The file contains alternating x/y arrays. Some of them throw a singularity error, some of them work, some of them give bad fit results albeit not throwing an error!. Unfortunately I can not spend the time on preparing each case. The following wrapper solves the issue for me in all cases and does not slow down the regression noticeably. I only tested it on the 450 data sets with fit order 2 and on the same amount of data with fit order 1, but not for higher orders. import PolynomialRegression from "ml-regression-polynomial";
export class NormalizedPolynomialRegression {
constructor(x, y, order) {
// Calculate normalization
const offsX = -Math.min(...x);
const factX = 1 / (Math.max(...x) - Math.min(...x));
const offsY = -Math.min(...y);
const factY = 1 / (Math.max(...y) - Math.min(...y));
// Apply normalization
const x1 = x.map((x) => (x + offsX) * factX);
const y1 = y.map((y) => (y + offsY) * factY);
// Regression on normalized data
const regression = new PolynomialRegression(x1, y1, order);
const normCoefficients = regression.coefficients;
// Retrive coefficients from normalized coefficients
let coeffs = Array(order + 1).fill(0);
coeffs[0] = normCoefficients[0];
for (let n = 1; n < order + 1; n++) {
const powers = calculatePowersOfElements(n);
const currentPreFact = normCoefficients[n] * factX ** n;
for (let j = 0; j < powers.length; j++) {
const currentExp = powers[j].powerA;
const currentFact = powers[j].factor * offsX ** powers[j].powerB;
coeffs[currentExp] = coeffs[currentExp] + currentPreFact * currentFact;
}
}
coeffs = coeffs.map((coeff) => coeff / factY);
coeffs[0] = coeffs[0] - offsY;
this.coefficients = coeffs;
}
predict(x0) {
let val = 0;
for (let n = 0; n < this.coefficients.length; n++)
val = val + this.coefficients[n] * x0 ** n;
return val;
}
}
function calculatePowersOfElements(n) {
const powers = [];
for (let i = 0; i <= n; i++) {
const aPower = i;
const bPower = n - i;
powers.push({
factor: binomialCoefficient(n, i),
powerA: aPower,
powerB: bPower,
});
}
return powers;
}
function binomialCoefficient(n, k) {
if (k < 0 || k > n) {
return 0;
}
if (k === 0 || k === n) {
return 1;
}
let result = 1;
for (let i = 1; i <= k; i++) {
result *= (n - i + 1) / i;
}
return result;
} Thanks for helping out. |
Hi,
for the data as shown in the example below, I get the following error if I try to fit well-behaved data with fit-order 2:
The x-data is monotonous, the y-data looks like a noisy parabola. Matlab has no issue with fitting.
Any ideas, why this is failing?
Example:
Thanks for your help.
The text was updated successfully, but these errors were encountered: