Minimal Rank Completions – Ethan N. Epperly

I’m delighted to share that my first applied mathematics paper, Minimal Rank Completions for Overlapping Blocks, coauthored with Nithin Govindarajan and Shivkumar Chandrasekaran, has been accepted for publication in Linear Algebra and its Applications. (We also have a preprint on arXiv.) In this post, I wanted to share what our paper is about and share an alternate derivation which ended up being cut from the final paper.

Our paper is concerned with the following question: given a collection of matrices which overlap in a particular way, can we choose the region of simultaneous overlap so as to minimize the rank of each of the individual matrices? This is a multi-objective optimization problem, so a priori it is not clear it has a simultaneous solution. So it was of great surprise to us when we discovered that it does. In fact, we were able to find a tractable algorithm to find all solutions to this multi-objective problem.

Our enormous thanks go to the anonymous reviewer, who went above and beyond by discovering and sketching to us a dramatically shorter and more revealing proof¹ of our main theorem. We are truly indebted to this extraordinary reviewer for the significantly streamlined and more understandable presentation in the current iteration of our paper.

For the remainder of this post, I want to discuss minimal rank completions in a little more generality and present a solution to a special case of a minimal rank completion problem which can be tractably solved. I will present a solution to this problem we discovered which I have not seen elsewhere in the literature. I hope that this perspective will be complementary to existing solutions to this problem published in the literature including the summary of this result in our paper.

Minimal Rank Completion Problems

Minimal rank completions have achieved a lot of buzz in statistics and data science. Given a matrix with unknown entries, it is often very natural to impute the missing entries as those minimizing the rank of the matrix. This is justified by a kind of Occam’s razor argument: big data matrices are very often (approximately) low-rank, so when data is missing, we may assume it takes whatever values are necessary to minimize the rank.

Finding the rank-minimizing choice of missing entries is, in general, NP-hard. However, under certain assumptions, semidefinite programming relaxations can sometimes exactly recover the missing entries.

Alternately, if the missing entries belong to a special pattern, it may be possible to find the rank-minimizing choice of the unknown entries using linear algebraic tools like matrix factorizations. These approaches have significantly more limited domains of applicability than optimization-based approaches, but have advantages in that they

can be more tractable as they involve matrix factorizations rather than solving optimization problems;
work over arbitrary fields of numbers, such as finite fields appearing in computer science;
can find all ways of choosing the entries to minimize the rank, in particular certifying or dis-certifying the uniqueness of the rank-minimizing choice; and
are guaranteed to find the rank-minimizer, without any statistical assumptions.

These algebraic methods have their roots in systems theory, integral operators, and rank-structured matrices. The last of these was the application which motivated our interest in the subject.

Our paper concerns an overlapping variant of this problem, where we simultaneously minimize the ranks of several matrices by choosing the entries in the overlap carefully. This problem emerged to us naturally in the construction of certain matrix representations, and we hope it might prove useful in tackling other problems. As it turns out, the overlapping problem can be solved very much in the spirit of a much simpler problem, the block $2\times 2$ minimal rank completion problem, which we will spend most of the remainder of this post discussing.

A Solution to the Block 2×2 Case

The block $2\times 2$ minimal rank completion problem is as follows: given a partially filled block matrix

(1) $\begin{equation*} \begin{bmatrix} A & B \\ ? & C \end{bmatrix} \end{equation*}$

how can the “?” be filled in to minimize the rank of this matrix?

A generalized version of this problem was originally solved by Kaashoek and Woerdeman. An alternate derivation using matrix factorizations is given by Eidelman, Gohberg, and Haimovici, though they only find some of the solutions to this problem. We seek to characterize all ways of choosing the “?” so that the rank is minimize the rank.

Here, I present the solution to this problem which my coauthors and I originally discovered, which is different than the one we summarize in the final version of our paper.² This solution is in the spirit of the one by Eidelman, Gohberg, and Haimovici but does produce all solutions.

Let’s start by recalling some facts about linear algebra. Given an $m\times n$ real³ matrix $K$ , one can define its column space, which I will denote $\operatorname{Col} K$ , to be the vector space consist of all linear combinations of the columns of $K$ . From this column space, or indeed any vector subspace of $\mathbb{R}^m$ , one can extract a basis for this subspace, meaning every vector in the subspace can be uniquely decomposed as a linear combination of elements from the basis. In this discussion, we shall always arrange the basis vectors as columns of a basis matrix $P$ . If we instead consider the row space $\operatorname{Row} K$ of $K$ , then we arrange the elements of a basis as rows of a matrix $Q$ .

Before we solve the problem, let’s reason about the lowest possible rank we could possibly expect for the completed matrix. Since the rank of a matrix can be no smaller than the rank of any of its submatrices, clearly we must have that, for any assignment $X$ of the “?”,

(2) $\begin{equation*} \operatorname{rank} \begin{bmatrix} A & B \\ X & C \end{bmatrix} \ge \operatorname{rank} \begin{bmatrix} A & B\end{bmatrix}. \end{equation*}$

However, in general, the rank of the completed matrix must be higher than $\operatorname{rank} \begin{bmatrix} A & B\end{bmatrix}$ , as is exemplified when $A$ and $B$ are both zero but $C$ is not. In addition to rank of $\begin{bmatrix} A & B\end{bmatrix}$ , we must also account for rows of $\begin{bmatrix} X & C\end{bmatrix}$ which cannot be written as linear combinations of the rows above, no matter how $X$ is chosen. With a little noodling, one can convince oneself that there are always at least $\operatorname{rank} \begin{bmatrix} B \\ C \end{bmatrix} - \operatorname{rank} B$ such rows, leading to the bound

(3) $\begin{equation*} \operatorname{rank} \begin{bmatrix} A & B \\ X & C \end{bmatrix} \ge \operatorname{rank} \begin{bmatrix} A & B\end{bmatrix} + \operatorname{rank} \begin{bmatrix} B \\ C \end{bmatrix} - \operatorname{rank} B =: r_{\rm opt}. \end{equation*}$

We shall show that, by judicious choice of $X$ , Eq. (3) can always be achieved with equality, making $r_{\rm opt}$ the minimal rank for this completion problem.

Let us now find such a rank-minimizing $X$ . The construction begins by considering the column spaces $\operatorname{Col} A$ and $\operatorname{Col} B$ of the matrices $A$ and $B$ . The intersection of these column spaces $\operatorname{Col} A \cap \operatorname{Col} B$ is again a vector subspace, and we choose a basis $P_{AB}$ for it. The subspace $\operatorname{Col} A \cap \operatorname{Col} B$ might have a smaller size than $\operatorname{Col} A$ . Therefore, to find a basis for $\operatorname{Col} A$ , we can extend the basis $P_{AB}$ by adding new columns $P_{\overline{A}}$ to it so that the enlarged matrix $\begin{bmatrix} P_{AB} & P_{\overline{A}} \end{bmatrix}$ forms a basis for $\operatorname{Col} A$ . Similarly, we can find new columns $P_{\overline{B}}$ to add to $P_{AB}$ so that the matrix $\begin{bmatrix} P_{AB} & P_{\overline{B}} \end{bmatrix}$ forms a basis for $\operatorname{Col} B$ .

Now comes something subtle. Since $P = \begin{bmatrix} P_{AB} & P_{\overline{A}} \end{bmatrix}$ forms a basis for $\operatorname{Col} A$ , every column in $A$ can be written as a linear combination of columns in $P$ . In matrix language, this means there exists a matrix $Q^\top$ such that $A = PQ^\top$ —in fact, this exact $Q$ forms a basis for $\operatorname{Row} A$ . Since $P$ is divided into two collections of columns, it is only natural to similarly (and conformally) divide $Q$ into two pieces as $Q = \begin{bmatrix} Q_{AB,A} & Q_{\overline{A},A} \end{bmatrix}$ . Thus, doing the same with $B$ as we did with $A$ , we obtain two matrix factorizations

(4) $\begin{equation*} A = \begin{bmatrix} P_{AB} & P_{\overline{A}} \end{bmatrix} \begin{bmatrix} Q_{AB,A}^\top \\ Q_{\overline{A},A}^\top \end{bmatrix}, \quad B = \begin{bmatrix} P_{AB} & P_{\overline{B}} \end{bmatrix} \begin{bmatrix} Q_{AB,B}^\top \\ Q_{\overline{B},B}^\top \end{bmatrix}. \end{equation*}$

Now we do the same song and dance with the row spaces of $B$ and $C$ . Let’s go through the construction somewhat quickly. We start with a basis $Q_{BC}$ for the intersection of $\operatorname{Row} B \cap \operatorname{Row} C$ . We then extend these to bases $\begin{bmatrix} Q_{BC} & Q_{\overline{B}} \end{bmatrix}$ and $\begin{bmatrix} Q_{BC} & Q_{\overline{C}} \end{bmatrix}$ for $\operatorname{Row} B$ and $\operatorname{Row} C$ . From here, we derive the existence of matrix factorizations analogous to Eq. (4):

(5) $\begin{equation*} B = \begin{bmatrix} P_{B,BC} & P_{B,\overline{B}} \end{bmatrix} \begin{bmatrix} Q_{BC}^\top \\ Q_{\overline{B}}^\top \end{bmatrix},\quad C = \begin{bmatrix} P_{C,BC} & P_{C,\overline{C}} \end{bmatrix} \begin{bmatrix} Q_{BC}^\top \\ Q_{\overline{C}}^\top \end{bmatrix}. \end{equation*}$

For the next part, we shall take advantage of a powerful fact: if I have a bases $P$ and $Q$ for the row and column spaces of a matrix $K$ , there exists a nonsingular matrix $R$ for which $K=PRQ^\top$ . Applying this fact to the bases $\begin{bmatrix} P_{B,BC} & P_{B,\overline{B}} \end{bmatrix}$ and $\begin{bmatrix} Q_{AB,B} & Q_{\overline{B},B} \end{bmatrix}$ for $B$ ‘s column and row spaces, we get the existence of a matrix $R = \begin{bmatrix} R_{BC,AB} & R_{\overline{B},AB} \\ R_{BC,\overline{B}} & R_{\overline{B},\overline{B}} \end{bmatrix}$ such that

(6) $\begin{equation*} B = \begin{bmatrix} P_{B,BC} & P_{B,\overline{B}} \end{bmatrix}\begin{bmatrix} R_{BC,AB} & R_{BC,\overline{B}} \\ R_{\overline{B},AB} & R_{\overline{B},\overline{B}} \end{bmatrix} \begin{bmatrix} Q_{AB,B}^\top \\ Q_{\overline{B},B}^\top \end{bmatrix}. \end{equation*}$

We now have all ingredients to describe the solution. Rather than trying to “derive” the solution in a rigorous way, let us try and discover the solution in a non-rigorous way and justify our work later. We’re hoping to find assignments $X$ of the “?” such that $\begin{bmatrix} A & B \\ X & C \end{bmatrix}$ achieves the minimum possible rank $r_{\rm opt}$ defined in Eq. (3). To do so, let’s try and find a rank factorization of the completed matrix and then infer what values $X$ will take. First off, let’s build a rank factorization for $\begin{bmatrix} A & B \end{bmatrix}$ using the building blocks we’ve already built

(7) $\begin{equation*} \begin{bmatrix} A & B \end{bmatrix} = \begin{bmatrix} P_{AB} & P_{\overline{B}} & P_{\overline{A} \end{bmatrix} \begin{bmatrix} Q_{AB,A}^\top & Q_{AB,B}^\top \\ 0 & Q_{\overline{B},B}^\top \\ Q_{\overline{A},A}^\top & 0 \end{bmatrix}. \end{equation*}$

Now we want to extend this to a rank factorization for the entire completed matrix. Let’s build up to this in stages, denoting by $\star$ entries whose value we have yet to determine. For us to have a hope of representing the matrix $C$ , we’ll need to somehow add $Q^\top_{\overline{C}}$ into our rank factorization. Doing exactly this, we get the partially specified rank factorization

(8) $\begin{equation*} \begin{bmatrix} A & B \\ X & C \end{bmatrix} = \begin{bmatrix} P_{AB} & P_{\overline{B}} & P_{\overline{A} & 0 \\ \star & \star & \star & \star \end{bmatrix} \begin{bmatrix} Q_{AB,A}^\top & Q_{AB,B}^\top \\ 0 & Q_{\overline{B},B}^\top \\ Q_{\overline{A},A}^\top & 0\\ \star & Q_{\overline{C}}^\top \end{bmatrix}. \end{equation*}$

Now, to fill in the second block row of the left factor, we recall that $C = P_{C,BC} Q_{BC}^\top + P_{C,\overline{C}} Q_{\overline{C}}^\top$ . From Eqs. (5) and (6), we deduce that $Q_{BC}^\top = R_{BC,AB} Q_{AB,B}^\top + R_{BC,\overline{B}} Q_{\overline{B},B}^\top$ . Thus, we can fill in more entries:

(9) $\begin{equation*} \begin{bmatrix} A & B \\ X & C \end{bmatrix} = \begin{bmatrix} P_{AB} & P_{\overline{B}} & P_{\overline{A} & 0 \\ P_{C,BC}R_{BC,AB} & P_{C,BC} R_{BC,\overline{B}} & \star & P_{C,\overline{C}} \end{bmatrix} \begin{bmatrix} Q_{AB,A}^\top & Q_{AB,B}^\top \\ 0 & Q_{\overline{B},B}^\top \\ Q_{\overline{A},A}^\top & 0\\ \star & Q_{\overline{C}}^\top \end{bmatrix}. \end{equation*}$

With these entries filled in, the remaining $\star$ ‘s can be chosen arbitrarily. Assigning names $F_{\overline{A}}^\top$ and $F_{\overline{C}}$ to these free variables, we conclude that

(10) $\begin{equation*} \begin{bmatrix} A & B \\ X & C \end{bmatrix} = \begin{bmatrix} P_{AB} & P_{\overline{B}} & P_{\overline{A} & 0 \\ P_{C,BC}R_{BC,AB} & P_{C,BC} R_{BC,\overline{B}} & F_{\overline{C}} & P_{C,\overline{C}} \end{bmatrix} \begin{bmatrix} Q_{AB,A}^\top & Q_{AB,B}^\top \\ 0 & Q_{\overline{B},B}^\top \\ Q_{\overline{A},A}^\top & 0\\ F_{\overline{A}}^\top & Q_{\overline{C}}^\top \end{bmatrix} \end{equation*}$

and

(11) $\begin{equation*} X = P_{C,BC}R_{BC,AB}Q_{AB,A}^\top + F_{\overline{A}} Q_{\overline{A},A}^\top + P_{C,\overline{C}} F_{\overline{C}}^\top. \end{equation*}$

From all the analysis previous, we know that all $X$ ‘s of the form Eq. (11) solve the minimal rank completion problem, making the completed matrix achieve the minimal rank $r_{\rm opt}$ defined in Eq. (3). With a little more elbow grease, one can also confirm that all such minimal completions $X$ are of the form Eq. (11), proving that Eq. (11) indeed characterizes all solutions to the minimal rank completion problem. This completes the characterization and construction of the complete set of minimizers to the block $2\times 2$ minimal rank completion problem.

The Overlapping Block Minimal Rank Completion Problem

If you found this post interesting, be sure to check out our paper (or here on arXiv) for an explanation of a different way of thinking about the solution of the block $2\times 2$ minimal rank completion problem and a solution to a more general “overlapping” variant. The treatment should be reasonably self-contained, and we hope the solution to this problem could prove a useful tool in tackling open problems in systems theory and the study of rank-structured matrices.

Minimal Rank Completion Problems

A Solution to the Block 2×2 Case

The Overlapping Block Minimal Rank Completion Problem

Leave a Reply Cancel reply