Questions tagged [nuclear-norm]

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

Filter by
Sorted by
Tagged with
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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 + \...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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\|...
user avatar
  • 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 ...
user avatar
  • 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 \...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ||...
user avatar
  • 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\|_* ...
user avatar
  • 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 \...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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&...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 \|_* =...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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^\...
user avatar
  • 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}\|...
user avatar
  • 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: \...
user avatar
  • 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}$$
user avatar
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 ...
user avatar
  • 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),$$ ...
user avatar
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 ...
user avatar
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:...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 \...
user avatar
  • 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 $\...
user avatar
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}\|...
user avatar
  • 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}\|...
user avatar
  • 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\...
user avatar
  • 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 ...
user avatar
  • 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 \| ...
user avatar
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}$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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,\...
user avatar
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 ...
user avatar
  • 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)$ ...
user avatar
  • 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}} $$ ...
user avatar
  • 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 ...
user avatar
  • 794