Constrained Matrix Inversion

  • Thread starter Nikratio
  • Start date
  • #1
13
0

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
marcusl
Science Advisor
Gold Member
2,699
361
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
13
0
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
marcusl
Science Advisor
Gold Member
2,699
361
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
13
0
Linear Programming was exactly the right keyword, thank you so much! I should be able to find my way from here on.
 

Related Threads for: Constrained Matrix Inversion

  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
2K
Replies
2
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
2K
Top