Questions tagged [nuclear-norm]
The nuclear norm of a matrix is the sum of its singular values.
127
questions
1
vote
0
answers
39
views
Nuclear norm of matrix comprised of points sampled uniformly at random from the hypersphere?
In a subfield of machine learning called "self-supervised learning", many methods constrain network representations to lie on the hypersphere. I want to understand how such representations ...
- 453
0
votes
0
answers
29
views
Relationship between trace norm (a.k.a. Schatten-1 norm) of a matrix and the vector norm of the matrix's row average?
I'm trying to understand whether a connection exists between two seemingly different optimization problems in machine learning.
Setup: Suppose I have $N$ points $x_1, ..., x_N \in \mathbb{R}^D$, where ...
- 453
2
votes
2
answers
168
views
Prove $ \| {\bf A}^2\|_* \leq \operatorname{tr}({\bf A}^\dagger {\bf A})$
I saw a lemma without any proof states that:
$$ \left\| {\bf A}^2 \right\|_* \leq \operatorname{tr} \left( {\bf A}^\dagger {\bf A} \right)$$
where $\bf A$ is an arbitrary square matrix and $\|\cdot\|_*...
1
vote
0
answers
24
views
Is the $k$-th elementary symmetric polynomial of the singular values the nuclear norm of the $k$-th alternating power of the matrix?
If $A$ is a complex $m$ by $n$ matrix, thus representing a $\mathbb{C}$-linear map from $\mathbb{C}^n$ to $\mathbb{C}^m$, we denote by $s_1, \ldots , s_r$ its singular values. Let $e_k$ denote the $k$-...
- 5,174
2
votes
1
answer
74
views
Proof of the variational formulation of the nuclear norm [closed]
How to show that the nuclear norm can be written in the following way?
$$\|X\|_* = \min\limits_{A,B: AB=X}\frac{\|A\|^2_2}{2} + \frac{\|B\|^2_2}{2}$$
Related: Variational characterization of nuclear ...
- 7,301
0
votes
2
answers
113
views
Gradient of the trace distance (Schatten $1$-norm) [closed]
Suppose that matrices $A$ and $B$ are Hermitian and positive semidefinite. How can I obtain the gradient of the trace distance between $A$ and $B$, i.e., $$C := \Vert A - B \Vert_1 := \mbox{Tr} \left( ...
- 113
1
vote
0
answers
59
views
Fast approximation minimizing the nuclear norm of weighed sum of matrices
Hi I am trying to find a rank-1 matrix within the space of a linear combination of known matrices:
$$ \boldsymbol{A} = \boldsymbol{A_0} + \sum_{m = 1}^{M} x_m \boldsymbol{B}_m $$
where $\boldsymbol{...
- 501
1
vote
1
answer
118
views
Nuclear norm minimization of a circulant matrix with fast Fourier transform
Given any vector $\boldsymbol{x}=(x_1,x_2,\cdots,x_n)^\top\in\mathbb{R}^{n}$, its circulant matrix can be written as follows,
\begin{equation}
\mathcal{C}(\boldsymbol{x})=\begin{bmatrix}x_1 & x_n &...
- 107
3
votes
1
answer
64
views
Relationship between weak and nuclear topologies
Let $(X,\Vert\cdot\Vert)$ be a Banach space. Is it always true that $X$ equipped with the weak topology $\sigma(X,X')$ is a nuclear space?
0
votes
0
answers
17
views
what is the Interpolation of Hermitian Toeplitz which owns a low-rank property?
I was studying Direction of Arrival (DOA) and I ran into an article that indicated that the
"desired covariance matrix is Hermitian Toeplitz and owns the low-rank property, the covariance matrix ...
- 13
0
votes
0
answers
248
views
Derivation of subgradient of a matrix's nuclear norm
I was going through the derivation of subgradient of the nuclear norm of a matrix from an old homework of a Convex Optimization course (CMU Convex Optimization Homework 2 - Problem 2).
The setup is ...
1
vote
1
answer
185
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 ...
- 9,230
5
votes
0
answers
204
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 ...
- 69
1
vote
0
answers
164
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
422
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
130
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,632
3
votes
1
answer
173
views
Positive semidefinite matrix ordering and nuclear 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,632
3
votes
0
answers
53
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 ...
- 113
2
votes
1
answer
113
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 \...
- 113
2
votes
1
answer
175
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
0
votes
2
answers
312
views
Maximize $\langle {\bf A} , {\bf X} \rangle$ subject to $\| {\bf X} \|_* \leq 1$
Given ${\bf A} \in \mathbb R^{m \times n}$, $$\begin{array}{ll} \text{maximize} & \langle {\bf A} , {\bf X} \rangle\\ \text{subject to} & \| {\bf X} \|_* \leq 1\end{array}$$ where $\| \cdot \|...
0
votes
1
answer
109
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,830
3
votes
1
answer
138
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 ||...
- 115
7
votes
0
answers
754
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\|_* ...
- 315
0
votes
1
answer
108
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,632
1
vote
0
answers
104
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 ...
- 321
0
votes
0
answers
455
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
34
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,632
1
vote
1
answer
73
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,632
3
votes
1
answer
85
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,632
0
votes
1
answer
134
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
250
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,632
0
votes
1
answer
241
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 ...
- 20
0
votes
1
answer
200
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,632
0
votes
0
answers
87
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,396
1
vote
1
answer
1k
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:
\...
- 152
1
vote
1
answer
80
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
162
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,396
1
vote
1
answer
161
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),$$
...
- 107
1
vote
0
answers
143
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 ...
- 107
1
vote
1
answer
467
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,963
1
vote
1
answer
137
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,396
4
votes
0
answers
940
views
Projection of a symmetric matrix onto the positive semidefinite (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 norm, i.e. ...
- 1,280
0
votes
1
answer
152
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
465
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
268
views
Proximal operator of the nuclear norm with non-negativity constraints
Let $\bf L$ and $\bf R$ be $n \times n$ matrices. Consider the following regularized least-squares problem
\begin{equation}
\mathbf{L} = \min_{\mathbf{L} \geq \mathbf{0}} \mu \|\mathbf{L}\|_* + \...
- 73
0
votes
0
answers
58
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}\|...
- 73
1
vote
1
answer
138
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\...
- 71
2
votes
0
answers
181
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 ...
- 71
0
votes
0
answers
195
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 \| ...
- 13