New answers tagged

1

A vector norm (in $\mathbb{R}^n$) is just a function $f:\mathbb{R}^n\to\mathbb{R}$ satisfying certain properties. If you put the positive homogeneity property together with the triangle inequality you get convexity of $f$: Let $\alpha\in[0,1]$, and $x,y\in\mathbb{R}^n$. Then $$f(\alpha x+(1-\alpha)y)\leq f(\alpha x)+f((1-\alpha)y)=\alpha f(x)+(1-\alpha)f(y)...


0

This is because of Cauchy-Schwarz'inequality. Indeed, you have to prove, for any $0\le\lambda, \mu\le1 $, $\lambda+\mu=1$, that $$\lVert\lambda a +\mu b\rVert\le \lambda\lVert a\rVert + \mu\lVert b\rVert $$ which is equivalent to \begin{align*} \lVert\lambda a +\mu b\rVert^2=\lambda^2\lVert a\rVert^2+\mu^2\lVert b\rVert^2 +2\lambda\mu\langle a,b\rangle &...


1

Hint: For any $x$ with $\|x\|_1=1$, we have $\|x\|_\infty \leq 1$.


0

If $\mathrm v \in \mbox{span} (\mathrm u_1, \mathrm u_2)$, then there is a $\mathrm x \in \mathbb R^2$ such that $\mathrm U \mathrm x = \mathrm v$, where the columns of $\mathrm U$ are $\mathrm u_1$ and $\mathrm u_2$. However, $\mathrm w \notin \mbox{span} (\mathrm u_1, \mathrm u_2)$. Thus, we have an instance of the famous least-squares problem $$\begin{...


0

Recall the following fact: The projection of a vector $\vec{w}\in\mathbb{R}^n$ onto a subspace $M\subset\mathbb{R}^n$ is the vector in $M$ closest to $\vec{w}$. In your case, the projection of $\vec{w}$ onto $\textrm{span}\{\vec{u}_1,\vec{u}_2\}$ is the parallel component (denoted $\vec{w}_{||}$). So, the minimum of $\|\vec{w}-\vec{v}\|$ where $\vec{...


1

Lets try the layman's approach: $$\vec v=\begin{bmatrix}a+b\\a-b\\a+b\\a-b\end{bmatrix}\ \ (a,b\in \Bbb{R})$$ We need to find $$\min_{a,b}||\vec v-\vec w||$$Check that the values of $a,b$ for which $||\vec v-\vec w||$ will be minimum $=$ values of $a,b$ for which $||\vec v-\vec w||^2$ will be minimum. Now $$\min_{a,b}||\vec v-\vec w||^2\\=\min_{a,b}\{(a+b-1)...


2

The condition number with respect to the norm induced by vector norm $\|\cdot\|$ is equal to $1$ precisely when the image of the ball $B_1=\{x:\|x\|\le 1\}$ is another ball $B_r$ of some radius $r>0$. For any vector norm that is not a constant multiple of the Euclidean one, there is a rotation of its unit ball that maps it into something other than a ...


0

Sparsity is actually the 0-norm or the Hamming distance to the 0 vector. Constant cost added whenever anything starts to differ from 0, but does not care by how much. So you can write sum(v1!=0), sum(v2!=0) % Hamming distance to 0 vector, a.k.a. 0 Norm. The thing is 1-norm minimization is able to approximate 0-norms better than 2-norm minimization (you ...


0

If you want to get v2 instead of v1 you have to minimize the 0 norm of your problem.


1

Here's a proof why $l^p(\mathbb N)$ is not locally convex, this is just for simplicity, it can be easily generalized. If it would be locally convex, then the unit ball $B_1(0)$ would contain a convex neighborhood U of $0$. Then there must be $\delta>0$ with $B_{2\delta}(0)\subset U$, hence also $\mathrm{conv}(B_{2\delta}(0))\subset U\subset B_1(0)$. Let ...


1

Your transition from the first line to the second is incorrect. We should have $$ \|x - \alpha\|^2 - \|x - \beta\|^2 = \\ (x - \alpha)^T(x - \alpha) - (x - \beta)^T(x - \beta) = \\ \|x\|^2 + \|\alpha\|^2 - \|x\|^2 - \|\beta\|^2 - x^T\alpha - \alpha^Tx + x^T\beta + \beta^Tx =\\ \|\alpha\|^2 - \|\beta\|^2 - 2\alpha^Tx + 2 \beta^Tx =\\ \alpha^T\alpha - \beta^T\...


0

Hint. Do you really expect that ties always occur in the triangle inequality? What if $B=-C\ne0$?


0

I've found two ways to reach an inequality similar to the one asked. 1. Similar to @CalvinKhor's answer but more precise: For a real Hilbert space $H$, the norm $ \big\| \,\cdot\, \big\|_{_{H}} $ is Fréchet-differentiable. Its derivative at, say, $0 \neq v \in H$ is $$\big(D\big\| \,\cdot\, \big\|_{_{H}} \big)\,v = \frac{⟨ \,\cdot\, , v\, ⟩...


0

First, let's show that $||f||_2 = \sqrt{\int_{[0,1]} f(x)^2 dx}$ is a norm. I will only prove that it satisfies the triangle inequality for norms: $$ ||f + g||_2 \leq ||f||_2 + ||g||_2. $$ This follows from noting that the scalar product $$ (f, g) = \int_{[0,1]} f(x) g(x) dx $$ satisfies the Cauchy-Schwarz inequality: https://en.wikipedia.org/wiki/...


1

It is an overkill, but I think it is an interesting one. $C^0(0,1)\subset L^2(0,1)$, hence we may assume that the functions we are dealing with have a Fourier-Legendre expansion in terms of shifted Legendre polynomials: they give an orthogonal complete base of $L^2(0,1)$ with respect to the usual inner product and by assuming $$ f(x)=\sum_{n\geq 0}c_n P_n(2x-...


0

Verify that: $$\|f\|_2 = \left( \int_0^1 |f(x)|^2 dx \right)^{1/2}$$ is a norm on $C([0,1])$ (hint for the triangle inequality: use the C-S inequality) Now $d_2(x,y) = \|x - y\|_2$, hence it is a metric


0

It suffices to show that for any $\beta$, there is a constant $C=C\left(\beta\right)$ such that for any non-negative $y$, $$\frac{1+y}{1+\beta y}\leqslant C.$$ Since $$\frac{1+y}{1+\beta y}=\frac 1\beta\frac{\beta-1+1+\beta y}{1+\beta y} =\frac{\beta-1}{\beta\left(1+\beta y\right)}+\frac 1{\beta}, $$ we have for any non-negative $y$, $$\frac{1+y}{1+\beta y}\...


1

Based on hints by Jyrki Lahtonen, here is the answer: We know that, the integral basis for $\mathbb{Q}[\xi_p]/\mathbb{Q}$ is $\{1,\xi_p, \ldots, \xi_p^{n-1}\}$ and the integral basis of $\mathbb{Q}[\zeta_p]/\mathbb{Q}[\xi_p]$ is $\{1,\zeta_p\}$. We will use above result to calculate discriminant: $$\text{disc}_{\mathbb{Q}}^{\mathbb{Q}[\zeta_p]}(1,\zeta_p,\...


1

No, this is not true. Take $p=3$ and $u=v = (1,1)$. Then the right side is $2$, while the left-side is $2^{1/3}2^{1/3}$. For a result somewhat in that direction see Hölder's inequality.


2

The $p$ "norm" fails to satisfy the triangle inequality for $p<1$.


2

Perhaps you mean $$\sum_{j=1}^n \|x_i\| \le n^{1/2} \left(\sum_{j=1}^n \|x_i\|^2\right)^{1/2}$$ which comes from the Cauchy-Schwarz inequality.


2

The fact: Any norms in a given finite-dimensional vector space are equivalent. And it is easy to check the space of $n\times m$ matrices is a finite-dimensional vector space; also the operator norm and infinity norm are really norms. So they are equivalent! i.e. $$||A||\le C_1||A||_{\infty}$$ and $$||A||_{\infty}\le C_2||A||$$ and that might be the ...


0

You seem to be confusing the random variable with its observed value. If $X$ and $Y$ are random variables (for example, $X$ is the result of the next roll of a six-sided die, and $Y$ is the result of the roll after that), then a statement like $P(X\ge 4) = P(Y\ge 4)$ is true whenever $X$ and $Y$ have the same distribution. But statement is false if you ...


2

Note that $$ \left (\sum_j a_{ij} x_j \right)^2 = \lvert \langle (a_{ij})_j, (x_j)_j \rangle \rvert^2 \leq \lVert (a_{ij})_j \rVert_1^2 \rVert x\lVert_1^2 $$ So, if $x$ is summable, you know that $\lVert x \rVert_1 < \infty$ and you can get rid of the norm of $x$ in the estimate. By $\langle \cdot,\cdot \rangle$ I mean the inner product in $\ell^1$.


1

One easy and effective option is to solve this problem using the proximal gradient method or FISTA (which is an accelerated version of the proximal gradient method). The proximal gradient method minimizes $f(x) + g(x) $ where $f $ and $g$ are convex and $f $ is smooth and $g$ is "simple", in the sense that the proximal operator of $g $ can be evaluated ...


1

Consider the problem $\min f(x) + \lambda \| x \|_{q}$ where $\lambda \geq 0$ and $f(x)$ is strictly convex. Also consider the related problem $\min f(x) $ subject to $\| x \|_{q} \leq \delta$. A common technique used in compressive sensing and other regularization schemes is to switch back in forth between these problems. This is most commonly ...


4

$\def\RR{\mathbb{R}}$ The bound is correct. Let $Q$ be the cube $[-1,1]^n$. So $V \cap Q$ is a bounded nonempty polytope and it must have a vertex, say $\vec{x} = (x_1, \ldots, x_n)$. After reordering the coordinates and negative signs as necessary, we may assume that $1 = x_1 = x_2 = \cdots = x_r > |x_{r+1}|$, $|x_{r+2}|$, ..., $|x_n|$. We claim that $r ...


0

Here's one way to prove it. Call your block matrix $K$. For any unit vector $v=\pmatrix{x\\ y}$, consider $\|Kv\|$ directly and show that it is bounded above by $\|A\|$. Then show that this upper bound is attainable for some $v$.


2

I've given this problem some thought over the last couple of days and while this is not an answer, it looks 'promising' in a sense and maybe someone else can take it further. Let$$f(x)=\frac{{\lVert x \rVert}_2}{{\lVert x \rVert}_{\infty}}$$ Notice that for all $\alpha \in \mathbb{R}\setminus{\{0\}}$ and all $x \in M\setminus{\{0\}}$ we have $f(\alpha\cdot ...


0

Assume that we work with the probability space $\left(\Omega,\mathcal F,\mathbb P\right)$. Then the following inequalities hold $$\mathbb P\left(A_i\right)=\mathbb P\left(\left\{2^i\mathbf 1_{A_i}\geqslant 2^i\right\}\right)\leqslant \mathbb P\left(\left\{\sum_{j=1}^{+\infty}2^j\mathbf 1_{A_j}\geqslant 2^i\right\}\right)\leqslant \mathbb P\left(\left\{\sum_{...


5

It is not always true. The following matrix is positive semidefinite with norm $3$: $$ P := \left(\begin{array}{ccc} 2 & 1 & 1\\ 1 & 2 & -1\\ 1 & -1 & 2\\ \end{array}\right) $$ Use $B$ to poke out the $-1$'s and you get $$ P \circ B = \left(\begin{array}{ccc} 2 & 1 & 1\\ 1 & 2 & 0\\ 1 & 0 & 2\\ \end{array}\...


1

I think this is true. Here's an attempt that looks potentially fruitful: Use the property given here. That is, note that $$ \DeclareMathOperator{\tr}{tr} \| P \circ B\| = \sup_{\|x\| = \|y\| = 1} x^*(P \circ B)y = \sup_{\|x\| = \|y\| = 1} \tr (D_x P D_y B^T) = \\ \sup_{\|x\| = \|y\| = 1} \langle D_x P D_y,B \rangle \leq \sup_{\|x\| = \|y\| = 1} \left(\...


1

Since $A^\ast A$ is positive semidefinite, it can be unitarily diagonalised as $A^\ast A=UDU^\ast$, where $U$ is unitary and $D=\operatorname{diag}(d_1,\ldots,d_n)$ is the eigenvalue matrix with $d_1\ge\cdots\ge d_n\ge0$. Since $U$ is unitary, the constraint $\|x\|=1$ is equivalent to $\|Ux\|=1$. Therefore \begin{align} \underline{\sigma}(A) &=\min_{\|x\|...


2

Short Answer: \begin{align} \left\|\begin{bmatrix} X\\A \end{bmatrix} \right\|^2_2 := \lambda_{max}\left(\begin{bmatrix} X\\A \end{bmatrix}\begin{bmatrix} X^\mathrm{*}&A^\mathrm{*} \end{bmatrix} \right) = \lambda_{max}\left(\begin{bmatrix}X^\mathrm{*} & A^\mathrm{*} \end{bmatrix}\begin{bmatrix} X\\A \end{bmatrix} \right) = \lambda_{max}\left(X^{*}X ...


1

Note that \begin{align*} \gamma & \geq\left\Vert \left[\begin{array}{c} X\\ A \end{array}\right]\right\Vert \\ & =\sup_{\left\Vert x\right\Vert =1}\left\Vert \left[\begin{array}{c} X\\ A \end{array}\right]x\right\Vert \\ & =\sup_{\left\Vert x\right\Vert =1}\sqrt{\left(\left[\begin{array}{c} X\\ A \end{array}\right]x\right)^{*}\left[\begin{array}...


3

It's not $A*A$, it's $A^*A$ where $A^*$ is the transpose of $A$. If you calculate $\operatorname{tr}(A^*A)$ (called the Frobenius norm$^\dagger$) you'll find that it equals $\|A\|$. $^\dagger$: Technically this is the square of the Frobenius norm.


3

In general, no. Consider $A=1\oplus\pmatrix{1&1\\ 1&-1}\oplus1$ and $W=1\oplus\pmatrix{1&0\\ 1&1}\oplus1$. We have $\|A\|_2=\sqrt{2}<\frac{1+\sqrt{5}}2=\|A_w\|_2$. As for your proposed conditions, here is a partial answer: When $A$ is entrywise nonnegative, $A^TA\ge A_w^TA_w\ge0$ entrywise. Hence the same order is preserved for their ...


1

Let your function be equivalent to $V=(BX-Y)'\cdot (BX-Y)$ $=(X'B'-Y')\cdot (BX-Y)$ $X'B'BX-2X'B'Y+Y'Y$ Now you can differentiate $V$ w.r.t $X$ and set it equal to 0. $2B'BX-2B'Y=0$ $B'BX=B'Y$ Thus $X=(B'B)^{-1}\cdot B'Y$ The equation above is related to the formula in linear regression.


1

Assuming $A$ is an orthogonal linear map (i.e. $A^T A = I$), you are correct that $\|Av\| = \|v\|$ does not hold in general for norms other than the $2$-norm. For example, take $$A = \frac{1}{\sqrt{2}}\begin{pmatrix}1 & 1 \\ -1 & 1\end{pmatrix}$$ which you can check satisfies $A^T A = I$, and $$v = \begin{pmatrix}1 \\ 0 \end{pmatrix}$$ and compute ...


1

Let $x=(x_1,x_2,\ldots,x_d)$. Then $\|x\|_1=|x_1|+|x_2|+\ldots+|x_n|$, $\|x\|_2=\sqrt{x_1^2+x_2^2+\ldots+x_d^2}$. Using inequality between arithmetic and quadratic mean: $$ \sqrt{\frac{x_1^2+x_2^2+\ldots+x_d^2}{d}}\geqslant \frac{|x_1|+|x_2|+\ldots+|x_d|}{d} $$ or $$ \|x\|_2\geqslant \sqrt{d}\cdot \|x\|_1, $$ as asked. Remark: to prove the QM-AM ...


2

The only example is $\Bbb C$. Say $A$ is a Banach algebra with the given property and say the identity is $e$. First suppose that $a$ is invertible and $\lambda\in\sigma(a)$, the spectrum of $a$. Then $|\lambda|\le||a||$. And $\lambda^{-1}\in\sigma(a^{-1})$, so $|\lambda^{-1}|\le||a^{-1}||=||a||^{-1}$. So $|\lambda|=||a||$. Now if $a$ is any element of $A$,...


0

First note that in the SVD of $A$, the diagonal entries of $D$ are guaranteed to be nonnegative. So the absolute values are unnecessary in the first definition of the trace norm. The two definitions of the trace norm are equivalent. Note that $A = UDV^T \implies A^T A = V D^T D V^T \implies A^T A V = V D^T D$, which shows us that the columns of $V$ form a ...



Top 50 recent answers are included