1
$\begingroup$

I reduced a problem of matrix completion to the problem

find $A,B$ such that

$AB=I$
$A_{min}\leq A \leq A_{max}$
$B_{min}\leq B \leq B_{max}$

One possible approach would be to just minimize $\|AB-I\|$ or minimizing $A$ and $B$ alternately. I was wondering whether there is a different, maybe more efficient approach to solve this. I know about the sign-accord-algorithm by Jiri Rohn to find strict bounds for the inverse of an interval matrix, but my matrix intervals are not necessarily regular.

In general I know the sign-pattern of the matrices, special cases are that one of the matrices is a (symmetrical) M-matrix. The symmetrical M-matrix case results in particular in a positive definite matrix.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ What do you mean by $\le$ for matrices? Elementwise bounds? Or the difference positive semidefinite? $\endgroup$
    – Robert Israel
    Commented Aug 16, 2016 at 21:33
  • $\begingroup$ I mean elementwise bounds. Some entries are in fact known so that the upper and lower bound are the same. $\endgroup$
    – bittertea
    Commented Aug 17, 2016 at 12:08

1 Answer 1

Reset to default
3
$\begingroup$

This is not an answer but rather a nasty warning. Suppose you have 2 by 2 matrices and you fix the diagonal elements at some $q\in(0,1)$ and want to look at the out of diagonal elements that should be in the interval $[-a,a]$ with $q^2+a^2=1$. Then the problem is perfectly solvable (just use $a$ for one of them and $-a$ for the other in both $A$ and $B$). Suppose however that you decided to start with $A=B=\begin{bmatrix}q&0\\0&q\end{bmatrix}$ (which, I believe, 99% of normal people would start with because it is "right in the middle of the square"). Then you'll be getting nowhere because any modification of $A$ or $B$ alone will merely create non-zero off-diagonal entries in $AB$ without changing the diagonal elements, so, unless your operator norm is something very perverted, you have a strict global minimum in each variable here without being anywhere close to the true answer. The moral is that whatever you do, you have to modify $A$ and $B$ simultaneously at some steps. It is an excellent optimization puzzle. I hope somebody will figure it out but whatever the algorithm is, the proof that it will find a solution if it exists should accompany it...

Improve this answer
$\endgroup$
3
  • $\begingroup$ Another thing this example shows is that the set of solutions may be disconnected, which is extremely disconcerting as far as general constraint problems go... $\endgroup$
    – fedja
    Commented Aug 17, 2016 at 14:17
  • $\begingroup$ When the bounds allow it, you may have some solutions with $\det(A) > 0$ and others with $\det(A) < 0$, but of course none with $\det(A)=0$, so again the set of solutions is disconnected. $\endgroup$
    – Robert Israel
    Commented Aug 17, 2016 at 21:33
  • $\begingroup$ @Robert Israel Indeed, though the disconnectedness in my example is even more malignant because it can proliferate (just consider the block matrix with $n$ two by two blocks; it will create $2^n$ components each of which can be destroyed by a separate restriction and, therefore, has to be caught by any "sure" algorithm. Thus, the complexity is at least exponential in $n$ :-( ) $\endgroup$
    – fedja
    Commented Aug 21, 2016 at 0:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .