5.3: Perturabtions Measured in the Frobenius Norm

We will now demonstrate that, for the multiplicative and additive perturbation cases where we minimized the induced 2-norm, we also minimized the Frobenius norm.

Let $A \in C^{m \times n}$, and let $rank(A) = r$.

$$\|A\|_{F} \triangleq\left(\sum_{j=1}^{n} \sum_{i=1}^{m}\left|a_{i j}\right|^{2}\right)^{\frac{1}{2}} \ \tag{5.8}$$

$$=\left(\operatorname{trace}\left(A^{\prime} A\right)\right)^{\frac{1}{2}} \ \tag{5.9}$$

$$=(\Sigma_{i=1}^{r} \sigma_{i}^{2})^{\frac{1}{2}} (\text{the trace of a matrix is the sum of its eigenvalues}) \ \tag{5.10}$$

$$\geq \sigma_{1}(A) \ \tag{5.11}$$

Therefore,

$$\|A\|_{F} \geq\|A\|_{2} \ \tag{5.12}$$

which is a useful inequality.

In both the perturbation problems that we considered earlier, we found a rank-one solution, or dyad, for $\Delta$:

$$\Delta=\alpha u v^{\prime} \ \tag{5.13}$$

where $\alpha \in \mathbb{C}$, $u \in \mathbb{C}^{n}$, $v \in \mathbb{C}^{n}$ such that $\|u\|_{2}=\|v\|_{2}=1$. It is easy to show that the Frobenius norm and induced 2-norm are equal for rank one matrices of the form in Equation (5.13). It follows from this that the $\Delta$ which minimizes the induced 2-norm also minimizes the Frobenius norm, for the additive and multiplicative perturbation cases we have examined. In general, however, minimizing the induced 2-norm of a matrix does not imply the Frobenius norm is minimized (or vice versa.)

Example 5.1

This example is intended to illustrate the use of the singular value decomposition and Frobenius norms in the solution of a minimum distance problem.

Solution

Suppose we have a matrix $A \in \mathbb{C}^{n \times n}$, and we are interested in finding the closest matrix to $A$ of the form $cW$ where $c$ is a complex number and $W$ is a unitary matrix. The distance is to be measured by the Frobenius norm. This problem can be formulated as

$$\min _{c \in \mathbb{C}, W \in \mathbb{C}^{n \times n}}\|A-c W\|_{F}\nonumber$$

where $W^{\prime}W = I$. We can write

$$\begin{aligned} \|A-c W\|_{F}^{2} &=\operatorname{Tr}\left((A-c W)^{\prime}(A-c W)\right) \\ &=\operatorname{Tr}\left(A^{\prime} A\right)-c^{\prime} \operatorname{Tr}\left(W^{\prime} A\right)-c \operatorname{Tr}\left(A^{\prime} W\right)+|c|^{2} \operatorname{Tr}\left(W^{\prime} W\right) \end{aligned}\nonumber$$

Note that $\operatorname{Tr}(W^{\prime}W) = \operatorname{Tr}(I) = n$. Therefore, we have

$$\|A-c W\|_{F}^{2}=\|A\|_{F}^{2}-2 \operatorname{Re}\left(c^{\prime} \operatorname{Tr}\left(W^{\prime} A\right)\right)+n|c|^{2} \ \tag{5.14}$$

and by taking

$$c=\frac{1}{n} \operatorname{Tr}\left(W^{\prime} A\right)\nonumber$$

the right hand side of Equation (5.14) will be minimized. Therefore we have that

$$\|A-c W\|_{F}^{2} \geq\|A\|_{F}^{2}-\frac{1}{n}\left|\operatorname{Tr}\left(W^{\prime} A\right)\right|^{2}\nonumber$$

Now we must minimize the right hand side with respect to $W$, which is equivalent to maximizing $\left|\operatorname{Tr}\left(W^{\prime} A\right)\right|$. In order to achieve this we employ the singular value decomposition of $A$ as $U \Sigma V^{\prime}$, which gives

$$\begin{aligned} \left|\operatorname{Tr}\left(W^{\prime} A\right)\right|^{2} &=\left|\operatorname{Tr}\left(W^{\prime} U \Sigma V^{\prime}\right)\right|^{2} \\ &=\left|\operatorname{Tr}\left(V^{\prime} W^{\prime} U \Sigma\right)\right|^{2} \end{aligned}\nonumber$$

The matrix $Z = V^{\prime} W^{\prime} U$ satisfies

$$\begin{aligned} Z Z^{\prime} &=V^{\prime} W^{\prime} U U^{\prime} W V \\ &=I \end{aligned}\nonumber$$

Therefore,

$$|\operatorname{Tr}(Z \Sigma)|^{2}=\left|\sum_{i=1}^{n} \sigma_{i} z_{i i}\right|^{2} \leq\left(\sum_{i=1}^{n} \sigma_{i}\right)^{2}\nonumber$$

implies that

$$\min _{c, W}\|A-c W\|_{F}^{2} \geq\|A\|_{F}^{2}-\frac{1}{n}\left(\sum_{i=1}^{n} \sigma_{i}\right)^{2} \ \tag{5.15}$$

In order to complete this example we show that the lower bound in Equation (5.15) can actually be achieved with a specific choice of $W$. Observe that

$$\operatorname{Tr}\left(W^{\prime} U \Sigma V^{\prime}\right)=\operatorname{Tr}\left(W^{\prime} U V^{\prime} \Sigma\right)\nonumber$$

and by letting $W^{\prime}= V U^{\prime}$ we obtain

$$\operatorname{Tr}\left(W^{\prime} A\right)=\operatorname{Tr}(\Sigma)=\sum_{i=1}^{n} \sigma_{i}\nonumber$$

and

$$c=\frac{1}{n} \sum_{i=1}^{n} \sigma_{i}\nonumber$$

Putting all the pieces together, we get that

$$\min _{c, W}\|A-c W\|_{F}^{2}=\sum_{i=1}^{n} \sigma_{i}^{2}-\frac{1}{n}\left(\sum_{i=1}^{n} \sigma_{i}^{2}\right)^{2}\nonumber$$

and the minimizing unitary matrix is given by

$$c W=\frac{1}{n}\left(\sum_{i=1}^{n} \sigma_{i}\right) U V^{\prime}\nonumber$$

It is clear also that, in order for a matrix to be exactly represented as a complex multiple of a unitary matrix, all of its singular values must be equal.