7
$\begingroup$

Let $A \in \mathbb{R}^{m\times n}$ and $\|A\| = \sum_{i, j} |A_{i,j}|$.

I am looking for constants $\alpha, \beta \in \mathbb{R}$ such that

$\alpha \|A\| \leq \|A\|_* \leq \beta \|A\|$

The function $\|\cdot\|_*$ is the Schatten-1 norm, or the sum of the singular values of $A$.

$\endgroup$
0

1 Answer 1

10
$\begingroup$

The best such inequality that depends only on $m$ and $n$ is: $$ \frac{1}{\sqrt{mn}}\|A\| \leq \|A\|_* \leq \|A\| $$ The right inequality is tight when $A$ is a matrix with a $1$ in the top-left corner and zeroes elsewhere. The left inequality is tight when $A$ is the matrix all of whose entries are $1$. These examples also show that you cannot get any better constants even if you let them depend on the rank of $A$.

To see that the inequalities actually hold, let's start with the left inequality. Write $A$ in its singular value decomposition: $$ A = \sum_i \sigma_i \mathbf{x}_i\mathbf{y}_i, $$ where $\{\sigma_i\}$ are the singular values of $A$ and $\{\mathbf{x}_i\}$ and $\{\mathbf{y}_i\}$ all have Euclidean norm $1$: $\|\mathbf{x}_i\| = \|\mathbf{y}_i\| = 1$ for all $i$. Then $$ \|A\| = \big\| \sum_i \sigma_i \mathbf{x}_i\mathbf{y}_i \big\| \leq \sum_i \sigma_i \big\|\mathbf{x}_i\mathbf{y}_i\big\| \leq \sqrt{mn}\sum_i \sigma_i \big\|\mathbf{x}_i\mathbf{y}_i\big\|_2 = \sqrt{mn}\sum_i \sigma_i = \sqrt{mn}\|A\|_*, $$ where $\|\cdot\|_2$ is the entrywise $2$-norm (sometimes called the Frobenius norm).

To see the right inequality, we recall that one formulation of the Schatten $1$-norm is as an infimum over all rank-$1$ decompositions of $A$: $$ \|A\|_* = \inf\big\{ \sum_i |c_i| : A = \sum_i c_i \mathbf{x}_i\mathbf{y}_i^*, \|\mathbf{x}_i\| = \|\mathbf{y}_i\| = 1 \big\}. $$

Well, one such rank-$1$ decomposition of $A$ is just the very naive one that writes it in terms of standard basis vectors $\{\mathbf{e}_i\}$: $$ A = \sum_{i,j} A_{ij} \mathbf{e}_i\mathbf{e}_j^*. $$

Since $\|A\| = \sum_{i,j} |A_{ij}|$, it follows immediately that $\|A\|_* \leq \|A\|$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.