Is a minimum a minimum in every norm? (for finite-dimensional vector spaces)

Question

I have a question regarding the equivalence of the norms in finite-dimensional vector spaces. Basically the question is: if $\hat{x}$ is some minimum-norm solution in a subspace $\mathcal{K}$ under euclidean norm, will it also be under other norms?

$\DeclareMathOperator*{\argmin}{arg\,min}$ Specifically, is the following statement correct?

$$\hat{x} = \argmin_{x\in\mathcal{K}}\|b - A x\|_2 \iff \hat{x} = \argmin_{x\in\mathcal{K}}\|b - A x\|_A $$

where $A$ is a symmetric positive definite square $n \times n$ matrix and $b, x$ are $n \times 1$ vectors.

Answer 1

Even for the special case of $\|\cdot\|_A$ it is not true. Let $N$ be the orthogonal complement of $K$. The minimum of $\|Ax-b\|_2$ occurs when $\nabla(\|Ax-b\|_2^2)\in N$, that is, $A^2x-Ab\in N$. Similarly the minimum of $\|Ax-b\|_A$ occurs when $A^3x-A^2b\in N$. In general, these are not the same.

For example, let $A=\begin{bmatrix}2&0\\0&1\end{bmatrix}$, $b=\begin{bmatrix}1&2\end{bmatrix}^T$, and $K=\{x:x_1+x_2=0\}$. The minimum of $\|Ax-b\|_2$ occurs at $x=\begin{bmatrix}0&0\end{bmatrix}^T$, while that of $\|Ax-b\|_A$ occurs at $x=\begin{bmatrix}2/9&-2/9\end{bmatrix}^T$.

Answer 2

The minimum depends on the norm you are using. Take $b=(1,1)^T$, $A=I_2$, $\mathcal K=span\{(1,0)^T\}$.

Then any point on the line between $(0,0)$ and $(2,0)$ is a solution of $$ \arg\min_{x\in\mathcal K} \|x-b\|_\infty, $$ while it holds $$ (1,0)^T=\arg\min_{x\in\mathcal K} \|x-b\|_p $$ for $p\in [1,\infty)$.