Hardness of a constrained quadratic maximization Consider the following quadratic maximization:
\begin{align}
\max_{\mathbf{x} \in \mathcal{X}} &amp;\quad\mathbf{x}^{T}\mathbf{A}\mathbf{x}
\end{align}
with
\begin{align}
\mathcal{X} = \lbrace
\mathbf{x} \in \mathbb{R}^{n} :~ \|\mathbf{x}\|_{2}=1, \|\mathbf{x}\|_{0}\le k
\rbrace,
\end{align}
where $\mathbf{A}$ is a positive semidefinite matrix and $k \le n$ is a sparsity parameter. 
This problem is NP-hard, by a reduction from the max-clique problem. 

I am interested in a similar problem obtained by imposing additional structure on $\mathcal{X}$.
In particular, assume that the $n$ variables in $\mathbf{x}$ are partitioned into $k$ disjoint groups.
We restrict the feasible set to unit-length vectors $\mathbf{x}$ with one active variable per group. 
That is, $\mathcal{X}$ contains again $k$-sparse vectors, but the support cannot be arbitrary; it contains (at most) one nonzero entry for each of the $k$ groups. 

Note that the feasible set in the modified problem is a subset of the previous maximization, but the number of feasible supports can still be exponential in the number of variables $n$ (for appropriately chosen $k$).

I suspect that the modified problem is also NP-hard. Any ideas on how to show that (or disprove)? Feel free to share your intuition.
(I have found the answer to my question, so I am sharing a sketch here).

The quadratic maximization can be shown to be NP-hard by a reduction from the following problem:


Given $k$-partite graph $G=(V_{1}, \dots, V_{k}, E)$, does $G$ contain a $k$-clique. 


Note that the latter problem is a (seemingly) special case of the max-clique problem restricted to a particular family of graphs. It can however be shown that it is also NP-complete by a reduction from the general max-clique problem itself (See here).

Let $\mathbf{A}$ denote the adjacency matrix of $G$.
Let $S$ be an arbitrary set of $k$ vertices and $\mathbf{A}_{S}$ denote the principal submatrix corresponding to $S$, i.e. $\mathbf{A}_{S}$ is the $k\times k$ adjacency of the graph induced by $S$.
If the vertices in $S$ form a $k$-clique in $G$, then all off-diagonal entries of $\mathbf{A}_{S}$ are equal to $1$, and its principal eigenvalue $\lambda_{1}(\mathbf{A}_{S}) = k-1$.
In any other case, that is, if $S$ is not a $k$-clique, then $\lambda_{1}(\mathbf{A}_{S}) &lt; k-1$.
Finally, note that since $G$ is $k$-partite, a $k$-clique (if one exists) will contain a single vertex from each of the sets $V_{i}$, $i=1,\dots,k$.

Let $\mathbf{A}^{\prime} = \mathbf{A} + |\lambda_{n}(\mathbf{A})|\cdot\mathbf{I}$, where $\lambda_{n}(\mathbf{A})$ is the smallest eigenvalue of $\mathbf{A}$; 
$\mathbf{A}^{\prime}$ is a PSD matrix.
Further, consider $k$ disjoint groups of variables corresponding to the sets $V_{1}, \dots, V_{k}$ of $G$.
We solve the quadratic maximization with input $\mathbf{A}^{\prime}$ and the specified groups of variables.
The maximum objective value will be equal to $k-1 + |\lambda_{n}(\mathbf{A})|$ if and only if $G$ contains a $k$-clique.