Conversion of minimization to maximization objective under Frobenius norm

Question

I want to understand how Schnass $^\dagger$ arrived at the maximising objective as described below (on page 5)

\begin{aligned} \displaystyle \min_{D,A} \Vert X-DA \Vert_F^2 &= \min_D \sum_n \min_{|I|\leq S} \Vert x_n -D_ID_I^{\dagger}x_n \Vert_2^2 \\ &= \Vert X \Vert_F - \max_D \sum_n \max_{|I|\leq S} \Vert D_ID_I^{\dagger}x_n \Vert_2^2 \end{aligned}

where $\dagger$ is the pseudo-inverse, $S$ denotes the cardinality of column vectors $a_n$ of matrix $A$.

---

^{$^\dagger$ K. Schnass, On the Identifiability of Overcomplete Dictionaries via the Minimisation Principle Underlying K-SVD, Applied and Computational Harmonic Analysis, 37(3):464--491, 2014.}

Answer 1

First, decompose

$$ \| x_n - A x_n \|_2^2 = \| x_n \|_2^2 + \| A x_n \|_2^2 - 2 \langle x_n, A x_n \rangle $$

In your case, $A = D_I D_I^{\dagger}$. By the properties of the Moore-Penrose pseudoinverse, we know that $D_I D_I^{\dagger} = D_I D_I^{\dagger} D_I D_I^{\dagger}$. Therefore,

$$ \| x_n - D_I D_I^{\dagger} x_n \|_2^2 = \| x_n \|_2^2 + \| D_I D_I^{\dagger} x_n \|_2^2 - 2 \langle x_n, D_I D_I^{\dagger} D_I D_I^{\dagger} x_n \rangle = \| x_n \|_2^2 - \| D_I D_I^{\dagger} x_n \|_2^2. $$

The rest follows from the fact that $\sum_{n} \|x_n \|_2^2 = \| X \|_F^2$ and the property $\min_{z} x - f(z) = x - \max_{z} f(z)$.

Another proof of the first decomposition: $D_I D_I^{\dagger}$ is a projection, so by the Pythagorean theorem you have

$$ \| x_n \|_2^2 = \| D_I D_I^{\dagger} x_n \|_2^2 + \| (I - D_I D_I^{\dagger}) x_n \|_2^2 \Rightarrow \| x_n - D_I D_I^{\dagger} x_n \|_2^2 = \|x_n\|_2^2 - \|D_I D_I^{\dagger} x_n \|_2^2. $$