I have a numerical high-precision badly conditioned over-constrained set of linear equations that I want to solve.

I start out with m=616 equations and n=585 unknowns for an equation of the form a.x = b. Since I would like to find any (approximate) solution and I expect the numerical errors to be small, I would like to truncate the number of equations to the number of unknowns so that there should be exactly one solution left.

However, even before doing that we run into trouble: MatrixRank[a] returns 533 while MatrixRank[a, Tolerance -> 0] returns 585, indicating a possible problem. Similarly NullSpace[a] returns something of dimensions {52,585} again indicating the redundancy of 52 equations. (Also indicating a problem LinearAlgebra`Private`MatrixConditionNumber[a] returns Infinity.)

Is there anyway to get anything out of these equations?

The offending problem,

a = CloudGet[
b = CloudGet[

LinearSolve[a, b]

produces the warnings: Result for RowReduce of badly conditioned matrix {...} may contain significant numerical errors and Linear equation encountered that has no solution.

I tried the procedure described in Solving a linear system with a badly conditioned matrix but when solving for y I run into the error "Linear equation encountered that has no solution."

  • 4
    $\begingroup$ Have you tried LeastSquares[a, b]? $\endgroup$
    – MarcoB
    Jun 8, 2022 at 14:40
  • $\begingroup$ @MarcoB, thanks. After about 10 mins it spits out a solution that when plugged back in has a small error for roughly 250~ equations and enormous errors for a lot of the others. I guess the initial numerical errors in a and b are too large despite using 200 digits precision. So this probably indicates that there is little to salvage here. $\endgroup$
    – Kvothe
    Jun 8, 2022 at 15:05
  • $\begingroup$ Also I was hoping this example could serve as a practice for a similar problem with additional positive definiteness constraints. Is there an equivalent of LeastSquares that allows positive definiteness constraints (on 2x2 matrices consisting of the x[i]). SemidefiniteOptimization only accepts a linear f which is why I thought I should be solving a truncated set of equations exactly rather than minimizing an error. Minimizing the error will involve squaring the terms in the objective. Can such a LeastSquares problem with these types of constraints still be solved in Mathematica. $\endgroup$
    – Kvothe
    Jun 8, 2022 at 15:13
  • $\begingroup$ (I think the problem is still supposed to be convex by the same logic that LeastSquares is convex despite using a quadratic objective.) $\endgroup$
    – Kvothe
    Jun 8, 2022 at 15:14


Your Answer

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