Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [nuclear-norm]

The nuclear norm of a matrix is the sum of its singular values.

0
votes
1answer
18 views

Logarithms of matrices that are close in trace distance are close?

Let us define the 1-norm or nuclear norm by the following expressions where $\dagger$ represents the conjugate transpose of a matrix. $$||A||_{1} = \text{Tr}(\sqrt{A^\dagger A})$$ The one norm ...
0
votes
1answer
79 views

Derivative of matrix nuclear norm

I'm trying to find the derivative of $$|(L^TL - \sigma)|_1 = \mbox{Tr} \left( \sqrt{(L^TL - \sigma)^\dagger(L^TL - \sigma)} \right)$$ with respect to $L$, where $\dagger$ is the transpose conjugate ...
0
votes
1answer
36 views

Revisit “Inequality between Frobenius and nuclear norm”

I am reading the following question: Inequality between Frobenius and nuclear norm I know $$\|X\|_* = \sum_{i=1}^r \sigma_i(X)$$and $$\|X\|_F = \bigg(\sum_{i=1}^r \sigma^2_i(X)\bigg)^{1/2}$$ I try ...
0
votes
0answers
8 views

the acceleration of nuclear norm of similar sub-problems, perhaps SVT?

i have come up with a model with two sub-problems. It looks like: $$ ||A||_* + \lambda_1||A-G-H_1||_F^2 $$ $$ ||B||_* + \lambda_2||B+G-H_2||_F^2 $$ So it involves two independent problems of solving ...
12
votes
2answers
270 views

If matrix $A$ has entries $A_{ij}=\sin(\theta_i - \theta_j)$, why does $\|A\|_* = n$ always hold?

If we let $\theta\in\mathbb{R}^n$ be a vector that contains $n$ arbitrary phases $\theta_i\in[0,2\pi)$ for $i\in[n]$, then we can define a matrix $X\in\mathbb{R}^{n\times n}$, where \begin{align*} X_{...
1
vote
0answers
106 views

“Shadow prices” interpretation of the dual certificate of nuclear norm optimization

In nuclear norm based matrix completion, there exists a low rank matrix $M$ of which only the indicies in $\Omega$ are sampled. Candes and Recht (2008) recover the original matrix using following ...
2
votes
2answers
544 views

When is the Frobenius norm bounded by the nuclear norm?

I am reading the Recht (2011) paper titled, "A Simpler Approach to Matrix Completion", and I cannot figure out the last inequality of the last line on page 3422 (page 10 of the document). The ...
1
vote
1answer
199 views

Derivative of the nuclear norm ${\left\| {XA} \right\|_*}$ with respect to $X$

The nuclear norm (also known as trace norm) is defined as \begin{equation} {\left\| M \right\|_*} = \mbox{tr} \left( {\sqrt {{M^T}M} } \right) = \sum\limits_{i = 1}^{\min \left\{ {m,n} \right\}} {{\...
2
votes
0answers
99 views

Nuclear norm and Schatten norm in practice

I have a problem where the regularizer is the nuclear norm and the matrix being regularized is $n \times d$ with $d < n$. I was initially not getting low rank for the desired performance, the ...
2
votes
1answer
547 views

Prove that nuclear norm of a matrix is equal to the sum of squares of Frobenius norm

Nuclear norm of a matrix is defined as the sum of the singular values of the matrix. I saw a Lemma (without any proof) claiming $$ \|X\|_\sigma = \min_{X=UV'} \|U\|\|V\| = \min_{X=UV'} \frac{1}{2}(\|...
1
vote
1answer
71 views

Low-rank matrix satisfying linear constraints linear mapping

Let $X \in \mathbb{R}^{m \times n}$ be a matrix that is assumed to be low rank. According to, Recht, Benjamin; Fazel, Maryam; Parrilo, Pablo A., Guaranteed minimum-rank solutions of linear matrix ...
3
votes
0answers
83 views

How does minimizing the rank of a matrix help us impute missing values in it?

I am not really a math guru myself, but I know that many estimation or approximation problems can be reformulated as minimizing the rank of a matrix. Although that is really hard, we can try to ...
1
vote
0answers
64 views

How to solve L1 optimization of Low-Rank matrix?

I am trying to solve the following problem but have some difficulties. Any ideas? Any leads? $$ \min_{A,C} \|C\|_* +\alpha\|X-A\|_1 \text{ s.t. } A=AC $$ $\|*\|_1$ is the sum of absolute values of ...
1
vote
0answers
85 views

Proof that nuclear norm minimization gives a unique solution

I am reading a paper "A simpler approach to matrix completion" Which talks about matrix completion using nuclear norm minimization. In section 4 it proofs that, the optimization problem gives a ...
2
votes
1answer
165 views

Lower bound nuclear norm of $A$ by $\mathrm{tr}(|A|)$

Let $A = (a_{ij}) \in \mathbb R^{n \times n}$ be a square matrix. Let $\|A\|_\ast$ be the nuclear norm of $A$. Is the following true? $$\sum_{i=1}^n |a_{ii}| \le \|A\|_\ast$$
1
vote
0answers
116 views

When does the nuclear norm fail to minimize rank?

Given $F$ and $G$, I'm solving the following problem: \begin{align} \min_{t} & \quad \mbox{rank}(A) \\ \text{s.t.}& \quad A = \text{diag}(t) F - G \\ \end{align} I used the nuclear norm, $\|...
4
votes
1answer
989 views

Inequality between Frobenius and nuclear norm

Let $M$ be a square matrix, $\|\cdot\|_*$ be the nuclear (trace) norm, and $\|\cdot\|_F$ be the Frobenius norm. The following inequality holds between the norms: $$\|M\|^2_* \leq \text{rank}(M) \|M\|^...
2
votes
0answers
422 views

Convex relaxation of rank constraint

I would like to approximate a symmetric matrix $X\in \mathbb{R}^{n\times n}$ by a matrix of rank no more than $r$, i.e., a matrix $Z=EE'$ where $E\in\mathbb{R}^{n\times r}$, for some given $r\leq n$. ...
4
votes
1answer
245 views

Is the nuclear norm equal to the Hilbert-Schmidt norm for a particular operator?

Suppose that $\varphi,\gamma\in L^2([0,1],\mathbb C)$ and define the operator $\varphi\otimes\gamma:L^2([0,1],\mathbb C)\to L^2([0,1],\mathbb C)$ by setting $\varphi\otimes\gamma=\langle\cdot,\gamma\...
1
vote
2answers
139 views

Matrix Differentiation of Fraction Power

I encounter a problem where I wish to calculate: $$ \frac{\partial}{\partial\boldsymbol{X}}\,\operatorname{tr}\left(\left( \boldsymbol{X X}^\top \right) ^{\frac{1}{2}}\right) $$ Peterson gave a very ...
1
vote
1answer
652 views

How to solve this minimization problem involving the nuclear norm?

Let $L$ and $R$ be $n \times n$ matrices. I am trying to solve the following minimization problem $$ L^{k+1} := \arg \min_{L} \lambda \|L\|_{\ast} + \frac{1}{2\mu}\|L-R^{k}\|_{F}^{2} $$ $$ \mbox{s.t.}...
9
votes
1answer
1k views

Sum of singular values of a matrix

Is there a "trick" to calculate the sum of singular values of a matrix $A$, without actually finding them? For example, the sum of the squared singular values is $\operatorname{trace}(A^TA)$.
0
votes
1answer
55 views

The derivative of a matrix operator

I want to solve for the following problem $$\min_{X \in \mathbb{R}^{2 \times2}}\{h(A(X))+\|X\|_*\}$$ where $\|\cdot\|_*$ is nuclear norm and $h:\mathbb{R}^{2}\to \mathbb{R}$: $h(y)=\frac{1}{2}\|B^{1/2}...
0
votes
2answers
70 views

Consecutive Proximal Projections?

I have a sparse matrix factorization problem, where I want to decompose a matrix $X\in \mathbb{R}^{n\times m}$ to $A\in \mathbb{R}^{n\times p}$ and $B\in \mathbb{R}^{p\times m}$, such that $X\approx ...
1
vote
1answer
371 views

Derivative of nuclear norm of $xx^T-V$

The function is $$f(x) = \| x x^T - V \|_*$$ where $\| \cdot \|_*$ denotes the nuclear norm and $V$ is a given matrix. $x$ is a vector. Please tell me how to differentiate $f(x)$. And, if it is ...
2
votes
2answers
521 views

Second derivative of the nuclear norm

The nuclear norm is defined in the following way $$\| X \|_* := \mbox{tr} \left( \sqrt{X^T X} \right)$$ and, from Derivative of the nuclear norm with respect to its argument, $$\frac{d}{dX} \| X \|...
3
votes
1answer
1k views

What's the proximal operator of the nuclear norm optimization problem?

\begin{equation} \arg\min_{X} \frac{1}{2}\|X-Y\|_{F}^2 + \tau\|X\|_{*} \end{equation} where $\tau\geq 0,Y\in \mathbb{C}^{n\times n}$ and $\|\cdot\|_{*}$ is the nuclear norm. What's the solution ...
3
votes
1answer
215 views

equivalent expressions for trace norm

I understand the trace norm (or nuclear norm) of a matrix $X\in\mathbf{R}^{n\times m}$is usually defined as $$\|X\|_{tr}=\sum_{i=1}^{\min\{m,n\}}\sigma_i$$ where $\sigma_i$'s are the singular values ...
2
votes
0answers
166 views

What's the spectral soft-thresholding operator when the matrices are complex?

\begin{equation} \begin{split} \min_{X} \, \frac{1}{2}\|X-Y\|_{\text{Fro}}^{2}+\lambda\|X\|_{*} \end{split} \end{equation} where $X, Y \in \mathbb{C}^{n \times n}$ and $Y$ is given. $\|\...
3
votes
1answer
750 views

How to convert the matrix completion problem to the standard SDP form?

Given the matrix completion problem defined below. \begin{equation} \begin{array}{ll} \text{minimize }{X \in \mathbb{R}^{m \times n}} & \sum_{(i,j) \in \Omega} ( X_{ij} - Z_{ij} )^2 + \lambda \...
1
vote
1answer
186 views

How to solve the constrained convex optimization problem with nuclear norm?

Let $f(x,y)=\sum_{i=1}^n\sum_{j=1}^{n}(x_{ij}+\sqrt{-1}y_{ij})B_{ij}(x,y)$ Now I want to solve the following problem: \begin{equation} \begin{split} &\arg\min_{C} \iint_{[0,1]^2}|(f_x+\...
1
vote
2answers
486 views

Revisit “How can I visualize the nuclear norm ball”

Revisit "How can I visualize the nuclear norm ball" Two eigenvalues are reproduced as following: $$ s_{1,2}=\frac{1}{\sqrt{2}}\sqrt{x^2+2y^2+z^2\pm|x+z|\sqrt{(x-z)^2+4y^2}}. $$ According ...
5
votes
0answers
718 views

What is the definition of the nuclear norm (aka trace norm, Ky-Fan n-norm) of a tensor?

What is the direct definition for the trace norm of a tensor? By direct I mean without matricization. Edit 1: By tensor, I mean a multi-way array, a generalization of vectors and matrices. (The ...
1
vote
0answers
102 views

Problem in defining weighted nuclear norm in CVX

I want to define a weighted nuclear norm, i.e., $$\|X\|_{w,*}=\sum_{i=1}^{m}{w_i\sigma_i(X)}$$ in CVX, but I can't. CVX has a function for nuclear norm called ...
2
votes
0answers
170 views

Polar set of orthogonal matrices set is nuclear norm ball

Reltated problems: Show that the dual norm of the spectral norm is the nuclear norm Prove that the nuclear norm is convex The set of orthogonal matrices is defined as: $$\mathcal{O}(n) = \{X\...
2
votes
1answer
512 views

Is there a nuclear norm approximation for stochastic gradient descent optimization?

I want to minimize $E$ by using stochastic gradient descent. I know that there is a sub-differential for the nuclear norm, but i want to know if is there a approximation of nuclear norm in order to ...
4
votes
0answers
776 views

Variational characterization of nuclear norm

The nuclear norm $||\cdot||_{*}$ of a matrix is defined as the sum of its singular values. Working from the result at the bottom of this blog post, we have, for a matrix $\mathbf{X}$ and its ...
2
votes
1answer
153 views

Nuclear norm regularization of symmetric matrix

I have an optimization problem of the form $$\min_{X \in \mathbb{R}^{n \times n}} g(X) - \lambda \|X\|_{*}$$ where function $g$ is convex and differentiable. I would like to use proximal gradient ...
2
votes
0answers
83 views

Simultaneous Rank Minimization

Consider a rank minimization problem over two positive semi-definite matrices $X$ and $Y$ with $R = \operatorname{rank}(X) = \operatorname{rank}(Y)$: \begin{equation*} \begin{aligned} & \underset{...
1
vote
1answer
113 views

Minimum of biconjugate of a nonconvex $f(x)$ is the minimum of $f(x)$ also?

In Fazel (2002) Matrix rank minimization with applications, Ch. 5.1.4-5.1.5, the author finds an analytic expression for the convex biconjugate of their nonconvex function; however, they state that ...
2
votes
1answer
299 views

Regularized Least Squares Using the Nuclear Norm

I have the following least squares nuclear norm problem, $$ \min_{\bf X} \frac{1}{2}{\left\lVert {\bf b} - {{\bf W}}vec({\bf X}) \right\rVert}^2_2 + {\lambda_*}\Arrowvert {\bf X} \Arrowvert_* $$ ...
3
votes
0answers
327 views

How to define the nuclear norm of a tensor?

As we know, the nuclear norm of a matrix $X$ is defined as follows $$\|X\|_{*} = \sum \sigma_{i}$$ where $\sigma_{i}$ is the $i$-th singular value of $X$. How to define the nuclear norm of a tensor $...
1
vote
2answers
264 views

Weighted least squares with nuclear norm minimization

Nuclear norm minimization is very popularization and formulation is least squares term with nuclear norm term as following, $$\min\limits_{X} \frac{1}{2}\|X_{3\times3}-Y_{3\times3}\|_F^2+\lambda\|X_{...
0
votes
1answer
143 views

How to get derivative of this matrix function?

I am trying to get the derivative of this function for use in a numerical optimization problem: $$f(\mathbf{T}) = ||\mathbf{TY_+}||_* + ||\mathbf{TY_-}||_* - ||\mathbf{T[Y_+, Y_-]}||_*$$ where $\...
8
votes
1answer
5k views

Show that the dual norm of the spectral norm is the nuclear norm

Could someone help me understand why the dual norm of the spectral norm is the nuclear norm? We can focus on the real field. Given a matrix $X \in \mathbb{R}^{m \times n},$ then the spectral norm is ...
1
vote
1answer
86 views

What is this norm $\|A\|_*$ called and what is it?

In my lecture notes I have found the notation $\|A\|_*$ for a matrix norm. Do you know the name of this norm (such that I can read the definition of it), or do you even know the definition of it? ...
6
votes
2answers
6k views

Prove that the nuclear norm is convex

For an $m \times n$ matrix, $A$, the nuclear norm of $A$ is defined as $\sum_{i}\sigma_{i}(A)$ where $\sigma_{i}(A)$ is the $i^{th}$ singular value of $A$. I've read that the nuclear norm is convex ...
9
votes
0answers
833 views

Rank, nuclear norm and Frobenius norm of a matrix.

The nuclear norm, denoted $\|\cdot\|_*$ is a good surrogate for the $rank$ when minimizing problems like $$\label{pb1}\tag{1} \min_X rank(X) : AX = B $$ Here, we're trying to find an matrix X with low ...
3
votes
2answers
1k views

Optimization of Frobenius Norm and Nuclear Norm

How to solve the following optimization problem, \begin{equation} \boldsymbol{\hat{x}} = argmin_{\boldsymbol{X}} \frac{1}{2} \| \boldsymbol{X - Y} \|_F^2 + \lambda \| \boldsymbol{X} \|_{*} \end{...
4
votes
0answers
61 views

The relation between $\inf_{R\in \mathsf{U}_n} \left\Vert A - BR\right\Vert^2_F$ and $\left\Vert AA^*-BB^*\right\Vert$

Suppose that $A$ and $B$ are two arbitrary $m\times n$ matrices with $m>n$. Let $\mathsf{U}_n$ denote the set of $n\times n$ unitary matrices. I'd like find positive constants $c_1$ and $c_2$ such ...