Questions tagged [nuclear-norm]
The nuclear norm of a matrix is the sum of its singular values.
115
questions
0
votes
0
answers
8
views
Matrix norm ordering upon multiplication by positive definite matrix
Assume I know the following to be true
\begin{equation}
||A||>||B||
\end{equation}
where $A$ and $B$ are $n\times n$ matrices and the norm can be any norm. If I define a positive definite matrix $...
- 282
1
vote
1
answer
69
views
Upper-bound for nuclear norm of $A \circ (v \otimes v)$ in terms of operator norm (or nuclear norm) of matrix $A$ and $L_\infty$-norm of vector $v$.
Let $A \in \mathbb R^{n \times }$ be a psd matrix such that $\|A\|_{op} \le r_1$ and $\|A\|_{*} \le r_2$. Let $v \in \mathbb R^n$ such that $\|v\|_\infty \le r_3$. Let $B:=A \circ V$ be the Hadamard ...
- 8,289
5
votes
0
answers
127
views
Weighted nuclear norm minimization
Crossposted on Operations Research Stack Exchange
The problem.
Let $X,A \in\mathbb{R}^{n\times m}$ and let $W\in\mathbb{R}^{nm\times nm}$ be a positive definite matrix. I want to know if there is a ...
- 248
1
vote
0
answers
86
views
What is proximal operator of nuclear norm in weighted space? (variable metric)
I am trying to find out proximal operator of nuclear norm in weighted space.
First, proximal operator of nuclear norm is
$$\text{prox}_{\lambda | \cdot |_*}(A) = \arg\min_X \frac{1}{2}\|X-A\|_F^2 + \...
- 11
0
votes
1
answer
122
views
What is the $1$-norm of a matrix?
Let $A \in \mathbb C^{n \times n}$ be some matrix. I'm trying to understand what $\lvert\!\lvert A \rvert\!\rvert_1$ means. I found two definitions:
$\lvert\!\lvert A \rvert\!\rvert_1$ is the ...
- 53
2
votes
1
answer
128
views
If $A\approx_\varepsilon D$, where $D$ is diagonal, is $A$ already almost diagonal?
Let $D$ and $A$ be symmetric positive semidefinite Hermitian matrices such that $\|D-A\|_1 \leq \varepsilon$, where $\|X\|_1 = \operatorname{tr}(\sqrt{X^*X})$. Moreover, let $D$ be diagonal.
Does ...
- 1,528
0
votes
0
answers
65
views
Estimate the nuclear norm of the diagonal part of a matrix.
Let $W = W_D + W_N$ be a rectengular matrix, split into a diagonal and non diagonal part. Let $X = U\Sigma V^*$ be a SVD of $X$ and $\sigma$ the vactor of singular values, then the nuclear norm is ...
2
votes
1
answer
52
views
Positive semidefinite matrix ordering and 1-norm of products
Let $A, A', B, B'$ be finite-dimensional, complex-valued, Hermitian, positive-semidefinite matrices. Moreover, let $(A-A')$ and $(B-B')$ also be positive-semidefinite.
The 1-norm is defined as $\|X\|...
- 1,528
3
votes
0
answers
41
views
Uniform continuity of $A\log A$
Let $A,B$ be finite dimensional full-rank positive semidefinite Hermitian matrices with unit trace. Let $|A-B|_1 \leq \varepsilon$ where $|X|_1 = \text{Tr}(\sqrt{X^*X})$ and $X^*$ is the transpose ...
- 103
2
votes
1
answer
28
views
Inequality for differences of ordered eigenvalues of nearby matrices
Let $A$ and $B$ be positive semidefinite finite dimensional matrices with unit trace such that $|A-B|_1\leq \varepsilon$ where one can choose any nonzero $\varepsilon$.
Let $\lambda_1\geq \lambda_2 \...
- 103
2
votes
1
answer
88
views
How calculate the trace norm via convex optimization?
I am taking the convex optimization course by CMU (though I am not a CMU student), and got stuck on this problem.
Formally, show that computing $\left \| X \right \|_{tr}$ can be expressed as the ...
- 21
1
vote
2
answers
201
views
Maximize $\langle \mathrm A , \mathrm X \rangle$ subject to $\| \mathrm X \|_* \leq 1$
Given $\mathrm A \in \mathbb R^{m \times n}$, $$\begin{array}{ll} \text{maximize} & \langle \mathrm A , \mathrm X \rangle\\ \text{subject to} & \| \mathrm X \|_* \leq 1\end{array}$$
Though I ...
- 18.9k
0
votes
1
answer
74
views
How do I minimize $||L||_* + \lambda ||S||_1$
Assume that we got a $n * m$ picture called $X$ and $X$ contains the noise picture $S$.
$X - S = L$ where $L$ is the clean filtered ideal picture and $X = L + S$ is the real picture taken by camera.
I ...
- 2,497
2
votes
1
answer
39
views
Does nuclear norm decrease as some elements in a matrix are set zero?
Let $M$ be a generic nonzero real matrix and $M_{0}$ is constructed by replacing some elements in $M$ with zero. Let $||\cdot||_{*}$ denotes the nuclear norm operator. Is it true that $||M||_{*}\geq ||...
- 105
5
votes
0
answers
406
views
Convex hull of rank-$1$ matrices is the nuclear norm unit ball
Let
$$A := \left\{ u v^T : u \in \mathbb{R}^m, v \in \mathbb{R}^n, \|u\|_2 = \|v\|_2 = 1 \right\}$$
I would like to show that
$$\textrm{conv}(A) = B_* := \left\{ X \in \mathbb{R}^{m \times n}: \|X\|_* ...
- 195
0
votes
1
answer
35
views
Relation between 1-norm of matrix and Euclidean norm of vectors
Suppose I have column vectors $u, v$ in a Hilbert space. I can define rank-1 matrices $uu^*$ and $vv^*$, where $^*$ denotes the transpose conjugate. If it is the case that
$$\|uu^* - vv^*\|_1 \leq \...
- 1,528
1
vote
0
answers
66
views
How to show that $ \mathcal{C}^{\infty} (\mathcal{M}, \mathbb{R}) $ is a nuclear space ?.
Let $ \mathcal{M} $ be a compact differential manifold.
Let $ A = \mathcal{C}^{\infty} (\mathcal{M}, \mathbb{R}) $ be the space of smooth functions over $ \mathcal{M} $.
How to show that $ A $ is a ...
- 311
0
votes
0
answers
130
views
Show that the nuclear norm is a norm
Let $A \in \mathbb{R}^{n\times m}$. Define
$$\|A\| = \sum_{i=1}^{\min(n,m)} \sigma_i$$
where $\sigma_i$ are the singular values of $A$. How to show that $\|A\|$ is norm?
We want to verify the ...
- 1
3
votes
0
answers
31
views
Discarding small eigenvalues to bound rank of a matrix
Suppose I have a diagonal matrix $D$ with nonnegative entries on the diagonal $\lambda_i$. Let the rank of $D$ be $r$. I am promised that $1-\delta \leq \sum_i\lambda_i \leq 1$ for some $0\leq\delta&...
- 1,528
1
vote
1
answer
50
views
Nuclear norm distance under Kronecker product
Let $A\otimes A$ denote the Kronecker product. Suppose $\|A - B\|_1 = \varepsilon$, where $\|\cdot \|_1$ is the nuclear norm a defined by $\|X\|_1 = \text{Tr}(\sqrt{X^\dagger X})$ and $X^\dagger$ is ...
- 1,528
3
votes
1
answer
62
views
Positive semidefinite ordering of matrices after small perturbations
We use the notation $A\leq B$ to denote that $B-A$ is positive semidefinite. The notation $|\cdot |_1$ denotes the nuclear norm i.e. $|X|_1 = \operatorname{Tr}\sqrt{X^*X}$, where $X^*$ is the ...
- 1,528
0
votes
1
answer
98
views
How to compare the nuclear seminorm of a matrix with the nuclear norm of the same matrix?
I know that the nuclear norm $\| \cdot \|_*$ is defined as the sum of the singular values ($\sigma_i$) of the matrix, that is for an $n\times n$ matrix $L$, the nuclear norm is defined by
$$\| L \|_* =...
4
votes
1
answer
210
views
Closest matrix that achieves positive semidefinite condition
Suppose we have two symmetric positive semidefinite $n$ dimensional matrices $A$ and $B$. We use the notation $X\leq Y$ means that $Y-X$ is positive semidefinite.
Suppose $A \not\leq B$ i.e. $B-A$ has ...
- 1,528
0
votes
1
answer
102
views
Relationship between $\|AB\|_*$ and $\|A\|_*\|B\|_*$
Suppose we have two matrices $A\in \mathbb{R}^{m \times n}$ and $B\in \mathbb{R}^{n \times p}$, then what's the relationship between $\|AB\|_*$ and $\|A\|_*\|B\|_*$? The notation $\|\cdot\|_*$ means ...
- 22
0
votes
1
answer
146
views
Smallest possible perturbation that decreases the rank of a matrix
Suppose I have some positive semidefinite matrix $A$ with rank $r$. I would like to write down a positive semidefnite matrix $B$ of rank $(r-1)$ such that $|A - B|_1$ is minimal where $|X|_1 = Tr[(X^\...
- 1,528
0
votes
0
answers
72
views
Minimization of Frobenius norm with nuclear norm penalization
Define $\mathcal{M}_n$ and $\mathcal{S}_n$ as the space of $n\times n$ real matrices and $n\times n$ symmetric real matrices, respectively. I want to solve the problem
$$
\min_{A\in S_n}\frac{1}{2}\|...
- 1,336
1
vote
1
answer
589
views
Singular values and trace norm of a submatrix
Let $A$ be an $ m \times n$ matrix where $ m \leq n $, and let $ B$ the matrix obtained from $A$ by removing both its first row and its first column. Let us denote the singular values of $A$ by:
\...
- 45
1
vote
1
answer
44
views
Decompose nuclear norm
Let $A$ and $B$ be two square matrices such that $A^\top B = 0$ and $B^\top A = 0$. How can we show that $$ \|A+B\|_{nuc} = \|A\|_{nuc} + \|B\|_{nuc}$$
- 35
2
votes
0
answers
112
views
Nuclear norm bounded by Frobenius norm
We have matrices $A,B\in\mathbb{R}^{n,m}$. Let $P\in\mathbb{R}^{n,n}$ and $Q\in\mathbb{R}^{m,m}$ be the orthogonal projection matrices in the column space of $A$ and the row space of $A$ (or column ...
- 1,336
1
vote
1
answer
131
views
Prove that $\|{X}\|_{*}=\min _{{A B}={X}}\|{A}\|_{F}\|{B}\|_{F}=\min _{{A B}={X}} \frac{1}{2}\left(\|{A}\|_{F}^{2}+\|{B}\|_{F}^{2}\right)$.
For any matrix $X\in\mathbb{R}^{m\times n}$, I am confused with
$$\|{X}\|_{*}=\min _{{A B}={X}}\|{A}\|_{F}\|{B}\|_{F}=\min _{{A B}={X}} \frac{1}{2}\left(\|{A}\|_{F}^{2}+\|{B}\|_{F}^{2}\right),$$
...
- 45
1
vote
0
answers
133
views
How to solve the truncated nuclear norm minimization problem to global optima?
Definition: Given a matrix $X\in\mathbb{R}^{m\times n}$ and a positive integer $r<\min\{m,n\}$, the truncated nuclear norm $\|X\|_{r,*}$ is defined as the sum of $\min\{m,n\}-r$ minimum singular ...
- 45
1
vote
1
answer
302
views
Nuclear norm of a block matrix
Suppose that
$$
X = \begin{bmatrix} A & C^T \\ C & B \end{bmatrix}
$$
where $X, A, B \succeq 0$ are (real) positive semidefinite matrices.
Is it true that the Cauchy-Schwarz like inequality:...
- 2,382
1
vote
1
answer
99
views
Subdifferential of the sum of two matrix norms
I've been reading the paper "Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion" by Koltchinskii et. al.
Let $\partial F(x)$ be the subdifferential of the convex ...
- 1,336
2
votes
0
answers
713
views
Projection of a Symmetric Matrix onto the Positive Semi Definite (PSD) Cone Under the Nuclear Norm
Question: Given a symmetric matrix, $S$, what is the solution to the optimization problem:
$$ \arg\min_{P \in \mathcal{S}_{\ge 0}} || S - P ||_N $$
where $|| \cdot ||_N$ denotes the nuclear ...
- 1,030
0
votes
1
answer
93
views
Nuclear norm of self-adjoint matrix
Consider first general matrices in $\mathbb{C}^{n \times m}$. Using norm duality, the nuclear norm (sum of singular values) can be expressed as
$$\|A\|_* = \max \{ | \langle A, B \rangle | : \|B\|_2 \...
- 1
0
votes
1
answer
274
views
Semi-definite programming, and bound on the trace distance
I'm quite new to semi-definite programming (SDP), and I'd like to compute a program that has some conditions on the distance between two vectors.
More precisely I have some fixed positive real $\...
- 125
2
votes
1
answer
196
views
Proximal Operator of the Nuclear Norm with Non Negativity Constraints
Let $L$ and $R$ be $n \times n$ matrices. Consider the following minimization problem
\begin{equation}
\mathbf{L} = \min_{L \geq \mathbf{0}} \mu\|\mathbf{L}\|_* + \dfrac{1}{2\lambda}\|\mathbf{L-R}\|...
- 43
0
votes
0
answers
55
views
Nuclear norm minimization of a matrix in the presence of non-negativity constraints [duplicate]
Let $L$ and $R$ be $n \times n$ matrices. Consider the following minimization problem
\begin{equation}
\mathbf{L} = \min_{L \geq \mathbf{0}} \mu\|\mathbf{L}\|_* + \dfrac{1}{2\lambda}\|\mathbf{L-R}\|...
- 43
0
votes
1
answer
65
views
How to prove the lower bound of the amount of perturbation on nuclear norm after scaling a matrix?
In my research, I need a lemma that gives the lower bound of the perturbation of nuclear norm. It is supposed to be
Statement. For any real matrix $M_{n\times n}$ and diagonal matrix $\Lambda_{n\...
- 51
2
votes
0
answers
145
views
How to solve truncated SVD problem with the constraint that the left and right singular vector spaces are the same?
Given $M \in \mathbb R^{n \times n}$, I would like to find its $k$-dimensional "leading singular vector space". $M$ is not necessarily symmetric. In contrast with the standard SVD problem, the left ...
- 51
0
votes
0
answers
139
views
How to convert the following optimization problem to SDP format?
I want to convert the optimization problem $x \in \mathbb R^n$ to SDP format to further solve it using the famous solvers like sdpt3 and sedumi.
$$\text{minimize} \quad \| A(x) - B \|_* + \lambda \| ...
1
vote
0
answers
55
views
Why is it robust and perturbed in matrix completion problem?
In matrix completion problem,
$$\min_{X} \mbox{rank}(X)~~s.t.~~x_{ij}=y_{ij},~\forall ij \in \Omega$$
where $X$ denotes the matrix to recover, $\Omega$ is the set of the known entries and $y_{ij}$ ...
- 119
0
votes
1
answer
53
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 ...
- 1,528
2
votes
1
answer
266
views
Trace Norm / Nuclear Norm: How to verify?
The nuclear norm is defined by this [from wikipedia]:
$$\|A\|_* = \text{trace} \left( \sqrt{A^*A} \right) = \sum_{i=i}^{\min\{m,n\}}\sigma_i(A)$$
I get the derivation of this equation. However, I ...
- 184
0
votes
1
answer
241
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 ...
- 1,528
2
votes
0
answers
167
views
Additivity of nuclear norm for projections
Let $A,B\in \mathbb R^{m\times K}$ with $B=U\Sigma V^T$. Let $r=\operatorname{rank} B$, $(u_1,\ldots,u_m)$ be the columns of $U$, and $S_1=\operatorname{span}(u_1,\ldots,u_r)$. Similarly let $(v_1,\...
- 32.3k
0
votes
1
answer
244
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 ...
- 643
2
votes
0
answers
56
views
How to get a simpler matrix representation of weighted nuclear norm?
Given a matrix $A \in \mathbb R^{n\times n}$, its nuclear norm is defined as
$$\|A\|_* = \sum_{i=1}^n\sigma_i(A)$$
where $\sigma_i(A)$ is the $i$-th singular value of $A$. Calculating $\sigma_i(A)$ ...
- 1,438
1
vote
0
answers
492
views
Orthogonal projection on nuclear-norm ball
Suppose that $w$ is an array of four $m\times n$ (real 0r complex valued) matrices: $w=(w_1, w_2, w_3, w_4) \in \mathbb{R}^{4mn}$.
Define
$$ \| w \|_{\text{nuc},1} = \sum_1^4 \| w_j \|_{\text{nuc}} $$
...
- 762
1
vote
2
answers
593
views
Prove that $\text{tr}(((A+B)^T(A+B))^{1/2}) \leq \text{tr}((A^TA)^{1/2}) + \text{tr}((B^TB)^{1/2})$
I'm trying to show that the nuclear norm (sum of singular values of the matrix) is actually a valid matrix norm. I know that
$$\sum\limits_{i=1}^n \sigma_i(A) = \text{tr}((A^TA)^{1/2})$$
So now what ...
- 794