Selecting $s \leq n$ rows can be done by left-multiplying $\rm A$ by a Boolean diagonal matrix with $s$ ones on its main diagonal. Hence, we have the following Boolean optimization problem

$$\begin{array}{ll} \text{minimize} & \| \mathrm A - \mbox{diag} (\mathrm x) \mathrm A \|_{\text{F}}^2\\ \text{subject to} & 1_n^{\top} \mathrm x = s\\ & \mathrm x \in \{0,1\}^n\end{array}$$

Note that

$$\mathrm A - \mbox{diag} (\mathrm x) \mathrm A = \left( \mathrm I_n - \mbox{diag} (\mathrm x) \right) \mathrm A = \left( \mbox{diag} (\mathrm 1_n) - \mbox{diag} (\mathrm x) \right) \mathrm A = \mbox{diag} (\underbrace{\mathrm 1_n - \mathrm x}_{=: \mathrm y}) \mathrm A = \mbox{diag} (\mathrm y) \mathrm A$$

Hence,

$$\begin{array}{ll} \text{minimize} & \| \mbox{diag} (\mathrm y) \mathrm A \|_{\text{F}}^2\\ \text{subject to} & 1_n^{\top} \mathrm y = n - s\\ & \mathrm y \in \{0,1\}^n\end{array}$$

where

$$\| \mbox{diag} (\mathrm y) \mathrm A \|_{\text{F}}^2 = \mbox{tr} ( \mathrm A^{\top} \mbox{diag}^2 (\mathrm y) \,\mathrm A) = \mbox{tr} ( \mathrm A^{\top} \mbox{diag} (\mathrm y) \,\mathrm A) = \mbox{tr} ( \mathrm A \mathrm A^{\top} \mbox{diag} (\mathrm y) ) = \langle \mathrm A \mathrm A^{\top}, \mbox{diag} (\mathrm y) \rangle$$

Let $\mathrm c \geq 0_n$ be the (nonnegative) vector whose $n$ entries are the entries on the main diagonal of the $n \times n$ Gram matrix $\mathrm A \mathrm A^{\top}$. Thus, we have the following *binary* **integer program** (IP) in $\mathrm y \in \mathbb Z^n$

$$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm y\\ \text{subject to} & 1_n^{\top} \mathrm y = n - s\\ & 0_n \leq \mathrm y \leq 1_n\\ & \mathrm y \in \mathbb Z^n\end{array}$$

We conclude that we select the $s$ rows of $\rm A$ with the $s$ largest $2$-norms. The minimum is the sum of the $2$-norms of the $n-s$ rows of $\rm A$ with the $n-s$ smallest $2$-norms.