Tag Info

New answers tagged

0

Thanks for asking this question. I have problems understanding the same thing. Particularly as follows. Although the nuclear norm is a relaxation for the rank, I don't understand how the nuclear norm can work as surrogate for minimising rank unless it is an upper bound for the rank. As was pointed out in the original post, the nuclear norm does not ...


3

Hint: Existence : Without loss of generality we can suppose x=0 (we could simply translate by x the set A). Uniqueness : Suppose there were $a_0,b_0∈A$ such that ||$a_0$∥=∥$b_0$∥=d and using the parallelogram law.


3

For each $p\ge 1$, we have $\|z\|_p=1$ so $|x|^p+|y|^p=1$. Geometrically, this is what happens as $p$ varies: (In the limit as $p\to\infty$, the edges sharpen to get a square.)


3

You can split your problem into $$ \min \|x\| \quad {s.t.} A_1 x = b_1, \ l_1\le x\le u_1, $$ and $$ \min \|y\| \quad {s.t.} A_2 y = b_2, \ l_2\le y\le u_2. $$ There is no coupling between both optimization variables.


0

You can use $$ I+BA^T=I+AA^T+(B-A)A^T. $$ Hence $$ \|(I+BA^T)(I+AA^T)^{-1}\|_2\leq 1+\|B-A\|_2\|A^T(I+AA^T)^{-1}\|_2. $$ By using the SVD of $A$, one can [from the fact that $x\mapsto x/(1+x^2)$ is for $x\geq 0$ bounded by $1/2$] get $$ \|A^T(I+AA^T)^{-1}\|_2\leq \frac{1}{2}, $$ so $$ \|(I+BA^T)(I+AA^T)^{-1}\|_2\leq 1+\frac{1}{2}\|B-A\|_2. $$ You can ...


0

Use the chain rule and the assumptions on $F$ to estimate the Sobolev norm of $\nu \circ F$, with respect to the Sobolev norm of $\nu$ and some constants depending on $F$.


2

Let $p(x)=(x-1)(x-2)\cdots(x-n-1)$. Then the polinom $p$ has degree $n$ and $\|p\|=0$ while $p\neq 0$ so the function in 1 is not a norm. Let $p=c$, $c$ is constant. Degree of $p$ is 0 and $p\neq 0$ but $\|p\|=\sup_{x\in [0,1]}|p'(x)|=0$ so 4 is not a norm.


0

You are on the right track. For the induced norm $\|A\|_\infty=\text{max}\frac{\|Ax\|_\infty}{\|x\|_\infty}$ we can also write the induced norm $\|A\|_\infty=\text{max}_{x \neq 0} (\|Ax\|_\infty)$ where $\|x\|_\infty = 1$. We know that the definition of the infinity norm on matrices is choosing the largest element. So follow these steps where ...


1

Let $x^{(M)}\in S_F$ be a sequence where $x_n^{(N)} = 1/n^2$ if $n\leq N$ and zero elsewhere. Note that $\sum_n 1/n^2 < \infty$. If $M>N$, then $||x^{(M)}-x^{(N)}|| = \sum_{k=N+1}^M 1/k^2\to 0$ as $N,M\to \infty$, so the sequence $(x^{(N)})_{N\in \mathbb{N}}$ is cauchy. Now we need to show that no point in $S_F$ can be the limit. Suppose $y\in S_F$ ...


0

You need to find a Cauchy sequence that is not convergent. In your case you could take an infinite sequence $\mathbf a$ such that $\|\mathbf a\|_1<\infty$, and approximate it by elements in $S_F$.


0

Start by noting that $S_F$ is a vector space and thus norms can be defined. To show that $||\cdot||\colon S_F\to \mathbb{R}_+$ defines a norm you need to prove that it satisfies the axioms for the norm. The structure of $S_F$ should make the proofs easier, since all sums are actually finite for a given $x\in S_F$. For example when proving $||\cdot||_2$ is a ...


2

Hint Prove that $a_j>0,\; \forall 1\le j\le n$ is the desired necessary and sufficient condition.


1

The question comes down to the following: if we know that $$ \sum_j a_j|x_j| = 0 \implies x_j = 0 \text{ for all }j $$ and if we know that $$ \sum_j a_j|x_j + y_j| \leq \sum_j a_j|x_j| + \sum_j a_j|y_j| $$ for every set of vectors $x$ and $y$, then what can we deduce about the values of $a_1,\dots,a_n \in \Bbb R$?


0

Hints: (only for the triangle inequality part) The first one follow from the canonical norm on the real line: $$ ||x + y||_1 = \sum |x_i + y_i| \leq \sum|x_i| + \sum|y_i| = ||x||_1 + ||y||_2$$ As for the second one, use the Cauchy Scharz inequality. The last one also follows from the canonical norm


0

No. A matrix specifies a linear operator, and you can clearly see that norms are not linear - for example, the norm of $a+(-a)=0$ is zero, but $||a||+||-a|| \neq 0$ unless $a$ is zero. However, if $a$ has non-negative components, note that $1^t a = ||a||$.


1

It follows from Cauchy's inequality: \begin{align*}(\|z\|+\|w\|)^2&=\|z\|^2+\|w\|^2+2\|z\|\|w\|\ge\|z\|^2+\|w\|^2+2|\langle z,w\rangle|\ge\|z\|^2+\|w\|^2+2\text{Re}\,\langle z,w\rangle\\&=\|z\|^2+\|w\|^2+\langle z,w\rangle+\overline{\vphantom{x}\smash{\langle z,w\rangle}}=\langle z,z\rangle+\langle z,w\rangle+\langle w,z\rangle+\langle ...


0

$\| A \|_2$ is bounded above by $\| A \|_F$ because we have $\| A \|^2_2 = \sigma_{max}(A)^2$ and $\| A \|_F = \sum_{i=0}^{{rank(A)}}\sigma_i^2$ $$\sigma_{max}(A) \le \sum_{i=0}^{{rank(A)}}\sigma_i^2 \Longrightarrow \| A \|^2_2 \le \| A \|^2_F $$ Since any norm is always positive, the squares of the norms follow this inequality if and only if the norms ...


0

Even in finite dimensions you can easily change the inner product. Let $\{ e_{n} \}$ be an orthonormal basis of $\mathbb{C}^{N}$ and define the new inner product $$ (x,y)_{\mbox{new}}=\sum_{n=1}^{N}\lambda_{n}(x,e_{n})(e_{n},y). $$ where $\lambda_{n} > 0$ for all $n$. All the norms are equivalent on $\mathbb{C}^{N}$. This can be written ...


1

First notice that $v^Tv$ is a scalar. Moreover $$\operatorname{tr}((vv^T)^Tvv^T)=\operatorname{tr}(vv^Tvv^T)=v^Tv\operatorname{tr}(vv^T)$$ and using the fact that $$\operatorname{tr}(AB)=\operatorname{tr}(BA)$$ we get that $$\operatorname{tr}((vv^T)^Tvv^T)=(v^Tv)^2$$ so we deduce the desired result easily.


0

Let $Q = vv^t$. And note that $v^t v$ is just a (nonnegative) number, so $$ \biggl\| \frac{Q}{v^t v} \biggr\| = \frac{\| Q \|}{v^t v} $$ so that all you need to prove is that $$ \| Q \| = v^t v. $$ Now, let $Q=[q]_{ij}$, then \begin{align} tr(Q) &= \sum q_{kk}\\ &= \sum v_k v_k \end{align} On the other hand, \begin{align} v^t v &= ...


1

This holds in $\mathbb R^n$ equipped with the $L^p$ norm if $1 \leq p < \infty$, while this fails if $p = \infty$.


2

Here is an approach to showing subadditivity: Let $B = \{x | \|x\|_s < 1\}$ and note that $B$ is convex (this is obvious if you draw a picture, also you could note that $B = B_2(0,1) \cap \{x | |x_1-x_2| < 1\|$). Let $\mu_B(x) = \inf\{ t > 0 | x \in t B \}$ (the Minkowski functional). Since $x \in (\|x\|_s+\epsilon)B$ for all $\epsilon$, we have ...


2

The convergence as for the norm means that $$ \| f - f_n\|_p \to 0 $$ Thanks to the Jensen inequality: $$ 2^{p-1} (|f(x)|^p + |f_n(x)|^p) - |f_n(x) - f(x)|^p \ge 0 $$ Now apply the Fatou theorem to get $$ \int \liminf \left[2^{p-1} (|f|^p + |f_n|^p) -|f_n - f|^p \right] \le \liminf\int \left[ 2^{p-1} \int (|f|^p + |f_n|^p) - \int |f_n - f|^p\right] $$ ...


0

Of course, $n:x\in M_{n,p}\rightarrow tr(\sqrt{x^Tx})$ can be derived in $x$ s.t. $x^Tx$ is invertible, that is, in the generic case when $n\geq p$ (if $n\leq p$, then consider $tr(\sqrt{xx^T})$). The result of greg is correct ; yet, his proof is unclear and I rewrite it for convenience. If $A$ is symmetric $>0$, then $f:A\rightarrow \sqrt{A}$ is a ...


-1

What about $|| M ||_{F} = \mathrm{Trace}(M^{T}M)$?


2

By definition, the norm $N(P)$ is the cardinality of the field $\mathcal{O}_K/P$. Since this is a finite field (the ideal norm is always finite in the ring of integers $\mathcal{O}_K$), it has characteristic $p$ with a prime $p$. It follows that $$ N(P)=p^{[(\mathcal{O}_K/P):\mathbb{F}_p]}. $$ Here $n=[(\mathcal{O}_K/P):\mathbb{F}_p]$ is the degree of the ...


3

Let $p$ be such that there is an inner product for which $\langle x,x\rangle=\lVert x\rVert^2_p$. Using the parallelogram identity $$\langle x+y,x+y\rangle+\langle x-y,x-y\rangle=2\langle x,x\rangle+2\langle y,y\rangle$$ with $x=(1,0,0,\dots)$ and $y:=(0,1,0,\dots)$, we get that $2^{2/p}=2$, hence $p=2$.


0

Any real inner product $(\cdot, \cdot)$ on any real vector space $V$, of finite dimension or not, defines a norm via $\Vert x \Vert^2 = (x, x)$ or $\Vert x \Vert = (x, x)^{1/2}$; the defining properties of the norm follow directly from the inner product axioms, which as I recall may be stated as: 1.) $(x_1 + x_2, y_1) = (x_1, y_1) + (x_2, y_1)$, $(x_1, y_1 ...


4

I imagine that you want to show that: If $N :X\to\mathbb R$ is $1-1$, then $d(x,y)=\lvert N(x)-N(y)\rvert$ is a metric. Clearly, the only property which needs checking is the triangular inequality. We have that $$ d(x,z)=\lvert N(x)-N(z)\rvert\le\lvert N(x)-N(y)\rvert+\lvert N(y)-N(z)\rvert=d(x,y)+d(y,z). $$ Note. The fact that $N$ is 1-1 guarantees ...


2

Fix $x\in H$ of norm $1$ and $\varepsilon>0$. Since $T_ix\to Tx$, we can find an integer $i_0$ such that if $i\geqslant i_0$, then $\lVert Tx\rVert\leqslant \lVert T_ix\rVert+\varepsilon$. We thus have that for $j\geqslant i_0$, $$\lVert Tx\rVert\leqslant \inf_{i\geqslant j}\lVert T_ix\rVert+\varepsilon$$ and taking the limit as $j$ goes to infinity, we ...


0

This is not hard to prove, just apply primary decomposition to both the ideal and its norm in integers. Then first show the statement for a prime norm, then conclude for the prime power norm. Finally, it is routine to check for a pair of coprime norms, the corresponding numbers of ideals obey the inequality from the truth for prime power norm. I lost myself ...


1

@ ziutek , I think that it is false. Take $\phi=\begin{pmatrix}86&38\\-51&-38\\51&-19\end{pmatrix},P=\begin{pmatrix}0.32&0.55&0.13\\0.58&0.05&0.37\\0.73&0.09&0.18\end{pmatrix}$. I find $||.||_2\approx 2.35$.


1

The $L_1$ norm has a big flaw: try to apply $K$-clustering in a 2d space, with 2 centroids. When you have to say which points are near to which centroid there's a high grade of uncertainty, since the surface wiht the same distance from both centroids has infinite (lebesgue) measure. (on the contrary, euclidean distance has only a line, so a 0-measure set). ...


1

Like the OP (see comment to Martin's answer), I had to convince myself of the correctness of Martin's excellent solution, and I worked it out. I'll just copy it here, in case it helps anybody else. First, an operator (matrix) $A$ is semipositive (positive semi-definite) if $x^T A X \geq 0 \,\forall x$. $C \leq D$ just means $D-C$ is positive ...


2

The key point is these properties about positivity of operators: if $0\leq C\leq D$, then $B^*CB\leq B^*DB$; and $C\leq \|C\|_{op}\,I$. You have then, using the positivity of the trace, $$ \|AB\|_{HS}^2=\text{Tr}(B^*A^*AB)\leq \|A^*A\|_{op}\,\text{Tr}(B^*B)=\|A\|^2_{op}\,\|B\|_{HS}^2. $$


1

Hint: Try to consider the easy case: $m=n=2$. In general case you can show that you obtain the inverse triangle inequality, i.e. $f(a+b)\ge f(a)+f(b)$.


0

In other words, you are being asked to answer this question : given a disc, $D$, placed anywhere on the real plane, what is the radius of the largest disc centred at the origin which has a non-empty intersection with $D$. To answer this, just draw a line from the origin to the centre of $D$ and pick the farthest point(from the origin) on this line which lies ...


3

Bounds for 2. and 3.: $2)$ Yes, $(t-1)$ is unbounded in $\mathbb{R}$, but your operator shift by $-1$ the values at where the function is applied $F(f)(t) = f(t-1)$. (And these functions are bounded, remember $ f \in C_b^0$), so it is well defined. Now to see it has a norm, $|F(f)(t)| = |f(t-1)| \leq \sup_t |f(t-1)| = sup_t|f(t)| = ||f||_\infty$. Hence ...


0

Let's define for brevity $\def\tr{\operatorname{tr}}\pi_x = \lvert x\rangle\langle x\rvert$, and $\Delta = \pi_v - \pi_w$, which is the operator the trace norm is taken of. Note that since $\Delta$ is hermitian, the trace norm of $\Delta$ equals the sum of the absolute values of its eigenvalues. Now $\Delta$ clearly has rank $2$ (except if $\pi_v=\pi_w$; in ...


3

You seem a bit confused in your reasoning for the first part. I'll give the solution for part 1, see if that helps. The operator norm of $F_1$ is one. The norm of $F_1(x)$ is $\sup x([0,9])$. The norm of $x$ is $\sup x([0,10])$. Because $x([0,9])$ is contained in $x([0,10])$, we have that the norm of $F_1(x)$ is no greater than the norm of $x$, so the ...


1

Maybe I am missing something, but since your norm is multiplicative, can't you just argue that if $ \|\|^*$ extends $\|\|$, you have for nonzero $a\in D$ $$\|aa^{-1}\|^* = 1$$ giving $$\|a^{-1}\|^* = \frac{1}{\|a\|^*} = \frac{1}{\|a\|}$$ because the starred norm extends $\|\|$? Thus you know for all invertible $a\in D$, your norm on inverses is the ...


0

If $i=j$ you get $$FT_N \cdot FT_N = \frac1N \sum_{k=0}^{N-1} \omega^{ik - ik} = \frac1N \sum_{k=0}^{N-1} 1 = 1$$ Note that $\sum_{k\in\mathbb Z_N}$ is the same as $\sum_{k=0}^{N-1}$. This is due to the definition of $\omega$ (actually dependent on $N$): $$\omega = e^{\frac{2\pi i}N}$$ So that $\omega^k = e^{\frac{2\pi ik}N}$ and $\bar\omega = \omega^{-1}$ ...


0

I presume that the balls are closed. $\Longleftarrow$ $x\in D_{2}\Rightarrow p_{2}\left(x\right)\leq1\Rightarrow p_{1}\left(x\right)\leq1\Rightarrow x\in D_{1}$ $\Longrightarrow$ If $D_{2}\subset D_{1}$ then $rD_{2}\subset rD_{1}$ for every $r\geq0$ so that: $x\in p_{2}\left(x\right)D_{2}\Rightarrow x\in p_{2}\left(x\right)D_{1}\Rightarrow ...


1

Suppose $D_1 \supset D_2$, then $ p_2(x)\leq 1 \implies p_1(x) \leq 1 $ since $p_2\left(\dfrac{x}{p_2(x)}\right) = \dfrac{p_2(x)}{p_2(x)} = 1$, we have $p_1\left(\dfrac{x}{p_2(x)}\right) = \dfrac{p_1(x)}{p_2(x)} \leq 1$ So $p_1(x) \leq p_2(x)$. The other direction is obvious.


0

Assume $p_1(x)\le p_2(x),\forall x\in\mathbb{R}^n.$ Take a vector $x$ such that $p_2(x)\le 1,$ that is, a vector in the unit ball $D_2.$ Since, $p_1(x)\le p_2(x)$ it is $p_1(x)\le 1.$ So $x\in D_1.$ This shows that $D_2\subset D_1.$ Conversely, assume that $D_2\subset D_1.$ Take $x\in D_2$ such that $p_2(x)=1.$ Since $D_2\subset D_1$ it is $p_1(x)\le 1.$ ...


2

Note that if $\lvert x_k\rvert=\max\{\lvert x_1\rvert,\ldots,\lvert x_n\rvert\}$, then for all $p$ $$ \lvert x_k^p\rvert\le \|x\|_p^p\le n\lvert x_k\rvert^p, $$ and hence $$ \lvert x_k\rvert\le \|x\|_p\le n^{1/p}\lvert x_k\rvert. $$ Thus $$ \lim_{p\to\infty}\|x\|_p=\lvert x_k\rvert=\max\{\lvert x_1\rvert,\ldots,\lvert x_n\rvert\}. $$


0

Hint: $$ \|x\|_\infty^p\le \| x \|_p^p \le n\|x\|_\infty^p $$


1

We consider $||.||_2$. Let $\sigma^2$ be the smallest eigenvalue of $AA^T$ (this is linked to the singular values of $A$). Then $||(\lambda I+AA^T)^{-1}||_2=\dfrac{1}{\lambda+\sigma^2}$. EDIT: Let $U=(\lambda I+AA^T)^{-1}$. Since $U$ is a symmetric $\geq 0$ matrix, $||U||_2$ is its greatest eigenvalue, that is $\dfrac{1}{\lambda+\sigma^2}$. Of course, ...


-1

For the first inequality, please use Lemma 4.1 in ref [X. X. Huang and X. Q. Yang. A unified augmented Lagrangian approach to duality and exact penalization. Mathematics of Operations Research, 28(3):533–552, 2003.] Note that $0<r\,/q<1$.



Top 50 recent answers are included