I have the following question. Let $A \in \mathbb{R}^{n \times m}$, with $n < m$, and let the columns of $A$ have unit $\ell_2$ norm. Say we select a set of indexes $I \subset \{0,1,\dots, m-1\}$ and call $A_I$ the matrix built using the columns of $A$ selected by those indexes. Can we define a relationship between the condition number of $A$ and the one of $A_I$?
Some numerical simulations suggest $\kappa(A) \geq \kappa(A_I)$, but I lack a formal proof of why this is the case, neither I'm sure this is always the case. Can you give me some proofs/references?
This is indeed always the case. This is easy to show using the variational characterization of singular values. We note that $\sigma_{\max}(A)$ is the equal to the maximum of the set $S_1$ given by $$ S_1 = \{\|Ax\| : \|x\| = 1\}. $$ On the other hand, $\sigma_\max(A_I)$ is the maximum of the set $S_2$ given by $$ S_2 = \{\|Ax\| : \|x\| =1 \text{ and } x_i = 0 \text{ for all } i \notin I\}. $$ Because $S_2 \subseteq S_1$, we can deduce that $$ \sigma_\max(A) = \max S_1 \geq \max S_2 = \sigma_\max(A_I). $$ Similarly, $$ \sigma_\min(A) = \min S_1 \leq \min S_2 = \sigma_\min(A_I). $$ It follows that $$ \kappa(A) = \frac{\sigma_\max(A)}{\sigma_\min(A)} \geq \frac{\sigma_\max(A_I)}{\sigma_\min(A_I)}. $$