3
$\begingroup$

Let $Y \in \mathbb R^{n \times c}$ and $r$ be an integer with $1 \le r \le \operatorname{rank}(Y)$. Consider the problem

$$\text{minimize} \|Y-X\|_{\text{Fro}}^2\text{ over }X \in \mathbb R^{n \times c} \text{ subject to rank}(X) \le r,$$ which seeks a $n$-by-$c$ matrix of rank $r$ which is closest to $Y$ w.r.t the Frobenius norm. The Eckart–Young–Mirsky theorem shows that the choice $X = \hat{Y}(r) := Y\Pi(r)$ solves this problem, where $\Pi(r) := V(r)V(r)^T$ the projection onto the subspace spanned by the first $r$ principal vectors $V(r) : = [V_1,\ldots,V_r] \in \mathbb R^{c \times r}$ of $Y$.

Question: What is $\hat{df}(r) := \operatorname{tr}\left(\frac{\partial vec(\hat{Y}(r))}{\partial vec(Y)}\right) = \sum_{i,j,k,l} \frac{\partial \hat{Y}_{ij}(r)}{\partial Y_{kl}}$ ?

Motivation: Such computations are necessary in applying SURE (Stein's Unbiased Risk Estimator) theory for tuning penalized least squares models, as a powerful alternative to cross-validation. Here "df" stands for "degrees of freedom" and is a measure of the complexity of the approximator model.

Observation: It's not hard to show that $$\hat{df}(r) \ge \hat{df}_{\text{naive}}(r),$$

where $\hat{df}_{\text{naive}}(r):= nc - (n-r)(c-r)$ is the least number of free parameters needed to completely specify an $n$-by-$c$ matrix of rank $r$. Theorem 5.2 of this paper computes the correction $\hat{df}(r) - \hat{df}_{\text{naive}}(r)$ exactly to be

$$\hat{df}(r) - \hat{df}_{\text{naive}}(r) = 2\sum_{k=1}^r \sum_{l=r+1}^{\operatorname{rank}(Y)}\frac{\lambda_l}{\lambda_k-\lambda_l} \ge 0, $$ where $\lambda_1 \ge \lambda_2 > \cdots > \lambda_r > \lambda_{r+1} \ge \cdots \ge \lambda_{\operatorname{rank}(Y)}$ are the eigenvalues of $Y^TY$. However, the method used by the referred paper is direct "brute-force" and involves some very long formulae. I was wondering whether there could be a cleaner (i.e synthetic) way to obtain this.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.