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