I reduced a problem of matrix completion to the problem

find $A,B$ such that

$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.

  • 1
    $\begingroup$ What do you mean by $\le$ for matrices? Elementwise bounds? Or the difference positive semidefinite? $\endgroup$ – Robert Israel Aug 16 '16 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 Aug 17 '16 at 12:08

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...

  • $\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 Aug 17 '16 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 Aug 17 '16 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 Aug 21 '16 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.