Fenchel conjugate of rank function

89 Views Asked by At

In the paper I am reading, they find the conjugate of the rank function$(f)$ of a rectangular matrix $X$ with bounded spectral norm($\|X\| \leq 1$), as follows $$ f^*(Y) = \sup_{\|X\|\leq 1} \operatorname{Tr}(X'Y)-f(X) $$ Using Trace inequality $Tr(X'Y) \leq \sum_{i} \sigma_i(X) \sigma_i(Y)$, and letting $X = U_x\Sigma_xV_x$ and $Y = U_y\Sigma_yV_y$ athe SVD of $X$ and $Y$, the paper assumes $U_x = U_y, V_x = V_y$ since $f(X)$ is independent of $Ux_, V_x$ and writes the conjugate as $$ f^*(Y) = \sup_{\|X\|\leq 1} \Sigma_i \sigma_i(X)\sigma_i(Y)-f(X) $$

Two concepts in the above constructions are not clear to me,

1) How one defines the rank of a rectangular matrix ?. Here it is assumed that $X$ is a rectangular matrix 2) Trace inequality says that equality holds only if the matrices are diagonalizable, and a rectangular matrix is not diagonalizable. In that case how can the equality in the final equation holds ?