Choosing the best submatrix

Question

Let $\mathbf{A}_{m\times n}$ be a matrix with non-negative elements. Assume that a submatrix $\mathbf{B}$ from $\mathbf{A}$ is defined as \begin{align} B_{i,j} = \begin{cases} A_{i,j}, & i\in\mathcal{I},\\ 0, & \text{otherwise}, \end{cases} \end{align} where $\mathcal{I}$ is a subset of $\{1,2,\cdots,m\}$.

For a constant size of $\mathcal{I}$, how does one should select $\mathcal{I}$ such that the following quantity becomes maximum $$\|\mathbf{B}^\mathrm{T}\mathbf{B}\|_1+\|\mathbf{B}\mathbf{B}^\mathrm{T}\|_1,$$ where $\|.\|_1$ is defined as the sum of the all elements of the matrix, and superscript $(.)^{\mathrm{T}}$ denotes the transpose operatrion.

Answer 1

You can solve the problem via integer programming as follows. For $i\in\{1,\dots,m\}$, let binary decision variable $x_i$ indicate whether row $i$ is selected. Then $B_{i,j}=A_{i,j}x_i$, so the problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^m A_{k,i} A_{k,j} x_k + \sum_{i=1}^m \sum_{j=1}^m \sum_{k=1}^n A_{i,k} A_{j,k} x_i x_j$$ subject to $\sum_{i=1}^m x_i = s$, where $s$ is the desired cardinality of $\mathcal{I}$. Now use a mixed integer quadratic programming (MIQP) solver.

Alternatively, you can linearize the quadratic objective by introducing a new decision variable $y_{i,j} \ge 0$, with $1 \le i < j \le m$, to represent the product $x_i x_j$. The resulting mixed integer linear programming (MILP) problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^m A_{k,i} A_{k,j} x_k + \sum_{i=1}^m \sum_{j=1}^m \sum_{k=1}^n A_{i,k} A_{j,k} y_{i,j}$$ subject to linear constraints: \begin{align} \sum_{i=1}^m x_i &= s\\ y_{i,j} &\le x_i \\ y_{i,j} &\le x_j \\ y_{i,j} &\ge x_i + x_j - 1 \end{align} Optionally, you can use the cardinality constraint to strengthen the formulation by including an additional constraint $$\sum_{i:i<j} y_{i,j} + \sum_{i:i>j} y_{j,i} = (s-1) x_j$$ for $j\in\{1,\dots,m\}$.