2
$\begingroup$

Let $F$ be the $n\times n$ DFT matrix, i.e., $F_{i,j} = \exp\left(-\tfrac{2\pi(i-1)(j-1)}{n}\imath\right)$, for $1\le i,j\le n$ and $\imath =\sqrt{-1}$. Futhermore, let $\Vert \cdot\Vert$ and $\odot$ denote the spectral norm and the Hadamard product, respectively.

For any $X\in \mathbb{R}^{n\times n}$, is there an explicit formula for $$\Vert F\odot X\Vert, \tag{$\star$}$$ in terms of $\Vert X\Vert$ or other simple functions of $X$? If instead of the spectral norm we had the Frobenius norm then the answer simply would have been the Frobenius norm of $X$. For $(\star)$, howerver, I guess the answer is negative. If my guess is correct, is there a reasonably sharp upper bound for $(\star)$?

$\endgroup$

1 Answer 1

2
$\begingroup$

I obtained the following upper bound. Let $D_z$ denote a diagonal matrix whose diagonal entries are given by vector $z$. Furthermore, write the SVD of $X$ as $X=UD_\sigma V^\mathrm{T}=\sum _{i=1}^r\sigma_i u_iv_i^\mathrm{T}$ where $r$ denotes the rank of $X$. Then we have \begin{align*} F\odot X &=\sum_{i=1}^r F\odot \left(\sigma_i u_i v_i^\mathrm{T}\right)\\ &= \left[\begin{array}{cccc} D_{u_1}&D_{u_2}&\dotsm&D_{u_r} \end{array}\right] \left(D_\sigma \otimes F\right)\left[\begin{array}{c} D_{v_1}\\ D_{v_2}\\ \vdots\\ D_{v_r} \end{array}\right]\\ &=\left[\begin{array}{cccc} \sigma_1D_{u_1}&\sigma_2D_{u_2}&\dotsm&\sigma_rD_{u_r} \end{array}\right] \left(I_{r\times r}\otimes F\right)\left[\begin{array}{c} D_{v_1}\\ D_{v_2}\\ \vdots\\ D_{v_r} \end{array}\right], \end{align*} where $\otimes$ denotes the Kronecker product. Now we can bound $\left\Vert F\odot X\right \Vert$ as \begin{align*} \left\Vert F\odot X\right\Vert & \leq \left\Vert\left[\begin{array}{cccc} \sigma_1D_{u_1}&\sigma_2D_{u_2}&\dotsm&\sigma_rD_{u_r} \end{array}\right]\right\Vert\left\Vert \left(I_{r\times r}\otimes F\right)\left[\begin{array}{c} D_{v_1}\\ D_{v_2}\\ \vdots\\ D_{v_r} \end{array}\right]\right\Vert\\ &=\sqrt{n} \left\Vert UD_\sigma \right\Vert_{\infty,2}\left\Vert V\right\Vert_{\infty,2}, \end{align*} where $\left\Vert\cdot\right\Vert_{\infty,2}$ is the maximum row-wise $\ell_2$-norm. There is also a simpler bound \begin{align*} \left\Vert F\odot X\right\Vert&\leq \left\Vert F\odot X\right\Vert_F\\ &=\left\vert X\right\Vert_F\\ &=\left\Vert\sigma\right\Vert_2, \end{align*} which can be sharper.

$\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.