[enhancement]: A is not a squre matrix

[haloinca]

Feature description

If there is a way to solve the case where $ A \in \mathbb{R}^{m \times n}, m > n $ is not a square matrix (number of rows is greater than number of columns)?

Minimum working example

using IntervalLinearAlgebra, LazySets, Plots
A = [2..4 -1..1;-1..1 2..4; -0.5..0.5 1..2]
b = [-2..2; -1..1; -0.1..0.1]
Xenclose = solve(A, b)
polytopes = solve(A, b, LinearOettliPrager())

Additional information

Is there any relevant literature to refer to?

[lucaferranti]

Hi @haloinca 👋 ,

First of all, I am very sorry for not replying. For some reason, your issue went unnoticed :/

That being said, yes there is some literature to solve non-square overdetermined interval linear systems. The idea is to define an "interval least square solution" and computing it reduces to solve a symmetric (hence parametric) square interval linear system. That can be solved with e.g. the currently implemented Skalna06 solver for parametric interval linear systems, although that's probably not the most efficient ways. There should be some more optimized approaches for the symmetric case. I'll double check the literature to find a couple of relevant papers

[haloinca]

Thank you for your reply. Reading your answer, I have another question. How do I convert an "interval least square solution" into a "symmetric square interval system"? Can you explain this in more detail? Or any reference is helpful.

[lucaferranti]

Hi again @haloinca 👋 ,

I am very sorry for the slow follow-up, quite a busy period 😅 . As a rule of thumb, if it takes more than one week to reply, feel free to ping me even every day until you get my attention, I try to reply as fast as possible, but sometimes I get driven away by the huge amount of notifications.

Coming back to your question. In general, a golden reference for interval linear algebra is Jaroslav Horacek phd thesis, available here it is a great general overview of interval linear systems (except for the parametric case) written in a very pedagogical easy to follow way. Particularly, overdetermined systems are described in chapter 6.

Elaborating a little, given an overdetermined interval linear system $\mathbf{Ax}=\mathbf{b}$, the square interval linear system is "simply" the linear system obtained as usual in linear least square, that is $\mathbf{A^T Ax}=\mathbf{A^T b}$.

Now, this is what is generally referred as "parametric interval linear system", because the elements in the matrix (and vector) are not independent intervals, but depend on some common variables (the elements of A). There are a few approaches to tackle this

1. Forget about the dependency and treat that as a normal interval linear system. That would lead to an huge overestimation of the solution set.
2. Use a parametric solver. This could be tricky because the elements of the matrix have nonlinear dependency (although there are algorithms for that).
3. Use the supersquare method, that is, solve the linear system (which is equivalent to the formulation above)

   \begin{pmatrix}
   I&A\\
   A^T&0
   \end{pmatrix}\begin{pmatrix}y\\x\end{pmatrix}=\begin{pmatrix}b\\0\end{pmatrix}

   This is "easier" than the previous one, because you have a linear dependency on the parameters, so could be solved e.g. with the Skalna06 method. Moreover, the thesis explores more tailored method to this specific problem.

If you have any other questions, do not hesiatate to ask, I'll try to answer quicklier next time.

Out of curiosity, do you need the overdetermined solver for a specific task? I'm asking because if this is blocking you in your work I'd be happy to bump this in my prioirity list

[haloinca]

Thank you for your patience and detailed reply, which gave me a general understanding of the interval linear system. In fact, I am a master student majoring in Electronic Engineering. I think the overdetermined solver can help me realize the interval identification problem of system parameters. I will try the methods you mentioned with the IntervalLinearAlgebra.jl toolbox.

As you may know, I am a novice to interval linear system, so there's no need to change the development plan for this impressive toolbox for my personal purposes.