Paradox on the derivative of the rank of a matrix

Question

It is clear that the function

$$f : \mathbb R^{m \times n} \to \mathbb N, \qquad X \mapsto \mbox{rank}(X)$$

has no derivative at all $X$ because the image of $f(X)$ assume values in the natural set. On the other hand, we know that the rank of any matrix can be computed by

$$\mbox{rank}(X) = \mbox{tr} \left( X^+ X \right) \tag{1}$$

where $\text{tr}$ is the trace operator and $X^+$ is the Moore-Penrose pseudoinverse of $X$. Notice, however, that the RHS of $(1)$ is differentiable everywhere (the trace operator and the pseudo inverse have derivatives) and it can be computed as

$$f'(X) = (X^T\otimes I_n)\left(-(X^+)^T \otimes X^+ \right) + (I_n \otimes X^+).$$

I am confusing if the rank has or not derivative at all points $X$. Probably I have made some mistake and I am missing something. I need some help. Thanks in advance!

Similar behavior happens with the nuclear norm (see Derivative of nuclear norm).

Answer 1

Your assumption that $f$ has no derivative anywhere is wrong.

In fact, the derivative exists and is $0$ almost everywhere.

Every matrix with full rank has a neighborhood of matrices that also have full rank, so in this neighborhood $f$ is constant and thus differentiable.

For matrices $X$ that do not have full rank, $f$ is not differentiable at $X$. (The pseudoinverse is not differentiable at such points either; it isn't even continuous).

Answer 2

Let's use a colon denote the trace/Frobenius product, i.e. $$A:B={\rm tr}(A^TB)$$ For $X\in{\mathbb C}^{m\times n}$ the differential of the pseudoinverse is $$\eqalign{ dX^+ &= X^+X^{+H}\,dX^H\,(I-XX^+) \cr &+\, (I-X^+X)\,dX^H\,X^{+H}X^+ \cr &-\, X^+\,dX\,X^+ \cr }$$

Now we are in a position to find the differential and gradient (with respect to $X$) utilizing the function that you proposed
$$\eqalign{ \rho &= {\rm rank}(X) \cr &= X^+:X^T \cr\cr d\rho &= X^+:dX^T + X^T:dX^+ \cr &= (X^+)^T:dX - X^T:X^+\,dX\,X^+ \cr &= (X^+-X^+XX^+)^T:dX \cr &= (0):dX \cr\cr \frac{\partial\rho}{\partial X} &= 0 \cr }$$ wherein the formalism of Wirtinger was used, i.e. treating $X$ and $X^H$ as independent variables, and choosing the simplest variable to work with.

For the case $X\in{\mathbb R}^{m\times n}$, we must handle all of the terms in the messy differential (after replacing the hermitian conjugates with simple transposes) $$\eqalign{ \rho &= X^T:X^+ \cr\cr d\rho &= X^+:dX^T + X^T:dX^+ \cr &= \Big[(X^+)^T:dX - X^T:X^+\,dX\,X^+\Big] \cr &\,\,\,\,\,\,\,+ X^T:X^+X^{+T}\,dX^T\,(I-XX^+) + X^T:(I-X^+X)\,dX^T\,X^{+T}X^+ \cr &= \Big[(0):dX\Big] + X^+X^{+T}X^T(I-XX^+)^T:dX^T + (I-X^+X)^TX^TX^{+T}X^+:dX^T \cr &= (I-XX^+)XX^+X^{+T}:dX + X^{+T}X^+ X(I-X^+X):dX \cr &= (X-XX^+X)X^+X^{+T}:dX + X^{+T}X^+ (X-XX^+X):dX \cr &= (0)X^+X^{+T}:dX + X^{+T}X^+(0):dX \cr &= (0):dX \cr\cr \frac{\partial\rho}{\partial X} &= 0 \cr }$$ and once again, the result is zero.