submatrix of a given size with maximum frobenius norm Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given  a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the following problem
\begin{align*}
\max_{I: |I|\le s} \|\mathbf{A}_{II}\|_F.
\end{align*}
Here $\mathbf{A}_{II}$ means the submatrix which picks columns and rows according to $I$. Stated differently I am interested in finding a submatrix of $\mathbf{A}$ of size $s\times s$ which has the largest Frobenius norm. Is there a simple tractable algorithm to do this. Please note that if I was asking for the Spectral norm instead of the Frobenius norm this would be an instance of sparse PCA and would be intractable in its most general form.
 A: Unfortunately, this problem is NP-Hard. Here's the argument.
Let $b_{ij} := |a_{ij}|^2$. Then, your problem is equivalent to
\begin{equation*}
   \max_x\quad \sum\nolimits_{ij} b_{ij}x_ix_j,\qquad x^T1=s,\ x \in \lbrace 0,1\rbrace^n,
\end{equation*}
where $x$ is an indicator vector telling which rows/cols are to be selected.
From this formulation it is obvious that a brute-force method that works in time $\binom{n}{s}$ suffices to solve this problem. 
Since $B=[b_{ij}] \ge 0$ (and symmetric), we can view $B$ as a weighted undirected graph. We can reduce the problem of finding a maximum clique to the above optimization problem (solution arrived at in discussion with S. Jegelka).


*

*Suppose the above problem is solvable in polytime for any $s$

*For a given weighted (with nonnegative weights) undirected graph, represent it via matrix $B$

*For $s=1,\ldots,n$ we solve the above problem, and test (in polytime) if any of the solutions is a clique (i.e., the submatrix $B_{I,I}$ is dense), and pick the largest such solution.


If step $3$ is polytime, then we can solve max-clique in polytime, which proves that your original problem is NP-Hard.
