Constrained Matrix Inversion

In summary, the author is looking for a constrained solution to a system of linear equations. He suggests using a linear programming approach.
  • #1
13
0
Hello,

I need to invert a non-square matrix A under the constraint that the absolute value of each component of the solution is less than some maximum. In other words, I want [tex]\vec{b}[/tex] such that [tex]A . \vec b = \vec c[/tex] and [tex]|b_i| < \alpha[/tex].

Are there any established methods for doing this?

My idea is to start with the pseudoinverse to compute the unconstrained solution, and to then add components [tex]\vec v_i[/tex] from the null space of A to satisfy the constraint. If this doesn't help, I wanted to consecutively add more basis vectors from the singular value decomposition of A, starting with the basis corresponding to the smallest singular value.

However, I don't see how to pick the coefficients of the [tex]\vec v_i[/tex] in such a way that the final solution is optimal in the sense that there is no other solution that satiesfies the constraints but has a smaller [tex]||A.\vec b - \vec c||[/tex].

Anyone able to help? Pointers to appropriate literature would be appreciated as well, I am not quite sure what keywords I should be looking for.
 
Physics news on Phys.org
  • #2
I see some confusion in your question, or at least nomenclature. You write b as a vector, in which case it certainly is not the pseudoinverse of A. It seems that you are asking for a constrained solution to a system of linear equations?
 
  • #3
Yeah, you're right.

What I want is a constrained solution to the system of linear equations.

At the beginning I was thinking that maybe I can construct a matrix [tex]A^+[/tex] such that [tex]\vec b = A^+ . \vec c[/tex] and [tex]\vec b[/tex] satisfies the constraint. Construction of [tex]A^+[/tex] would then be a "constrained matrix inversion". But I no longer think that such a matrix can exist, so my problem is indeed to find a constrained solution to a system of linear equations.
 
  • #4
One possible approach is to couch it as a linear programming problem that can be solved by the simplex method. This method solves systems of linear equations subject to simple constraints.

In this case you would minimize Ix, where I is the identity matrix, subject to the constraint
Ax < b
where the vector b has components alpha. A web search should turn up dozens of sites on simplex method and linear programming, and it is also covered in texts on numerical analysis.

I expect there's also a variant available somewhere to deal with the absolute value I|x|, or some means to reset any value that goes negative.
 
  • #5
Linear Programming was exactly the right keyword, thank you so much! I should be able to find my way from here on.
 

What is constrained matrix inversion?

Constrained matrix inversion is a computational technique used to find the inverse of a matrix that satisfies certain constraints or conditions. These constraints can be related to the structure or properties of the matrix, such as symmetry, sparsity, or positive definiteness.

Why is constrained matrix inversion important?

Constrained matrix inversion is important because it allows us to efficiently solve mathematical problems that involve inverting matrices with specific properties. This includes a wide range of applications in fields such as statistics, engineering, and physics.

What are some common constraints used in matrix inversion?

Some common constraints used in matrix inversion include symmetry, sparsity, positive definiteness, and diagonal dominance. These constraints can help reduce the computational complexity of finding the inverse and improve the accuracy of the solution.

What are some methods for performing constrained matrix inversion?

There are several methods for performing constrained matrix inversion, including direct methods such as Cholesky decomposition and LU decomposition, as well as iterative methods such as conjugate gradient and Gauss-Seidel. The choice of method depends on the specific problem and the constraints involved.

What are the limitations of constrained matrix inversion?

Constrained matrix inversion can be limited by the size and complexity of the matrix, as well as the constraints used. Some constraints may also be difficult to satisfy, leading to increased computational time or reduced accuracy. Additionally, round-off errors and numerical instability can also affect the accuracy of the solution.

Suggested for: Constrained Matrix Inversion

Replies
2
Views
2K
Replies
4
Views
163
Replies
24
Views
337
Replies
1
Views
1K
Replies
3
Views
936
Replies
5
Views
909
Replies
4
Views
972
Replies
3
Views
896
Replies
7
Views
323
Back
Top