Tag Info

Hot answers tagged

5

Frobenius Norm Case We first introduce a lemma. Lemma 1. If $A, B$ are respectively $m \times n$ and $n \times p$ matrices, then $\|AB\| \le \|A\|\|B\|$. Proof. Note that $AB$ has columns $A\vec{\beta}_1, \dots, A\vec{\beta}_p$ where $\vec{\beta}_j$ is the $j$th column of $\beta$. So$$\|AB\|^2 = \sum_{j=1}^p \|A\vec{\beta}_j\|^2 \le \sum_{j=1}^p ...


5

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.)


5

Not necessarily. For example, we can take $$ A = \pmatrix{1&0\\0&1}, \quad B = \pmatrix{1&1\\0&1} $$ the only eigenvalue of $A-B$ is $0$, so $A \geq B$. However, $\|A\|_2 = 1 < \|B\|_2$. Regarding your update: when $A,B$ are symmetric, this amounts to showing that if $A,B,$ and $A-B$ are positive semidefinite, then $\|A\|_2 \geq ...


4

In general, any symmetric positive definite $W$ induces the norm $\|x\|_W=\sqrt{x^TWx}=\|W^{1/2}x\|_2$ on $\mathbb{R}^n$. The matrix norm induced by $\|\cdot\|_W$ can be related to the spectral norm as $$ \|A\|_W =\max_{x\neq 0}\frac{\|Ax\|_W}{\|x\|_W} =\max_{x\neq 0}\frac{\|W^{1/2}Ax\|_2}{\|W^{1/2}x\|_2} =\max_{y\neq ...


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.


3

Submultiplicative norms for non-square matrices obviously do not make sense, but with square matrices, I don't think what you originally wrote was wrong. More specifically, we have the following Proposition. Suppose $A,B\in M_n(\mathbb C)$. If $\rho(AB)=\|AB\|_\square\le1$ for some submultiplicative norm $\|\cdot\|_\square$, then there exists some ...


3

We have $$(x,y)\in B(0,1)\iff N(x,y)=\sup_{t\in\mathbb{R}}\frac{|x+ty|}{t^2+t+1}\le1\iff |x+ty|\le t^2+t+1, \forall t\in\Bbb R\\\iff -t^2-t-1\le x+ty\le t^2+t+1,\forall t$$ the second inequality gives $$t^2+(1-y)t+1-x\ge0,\forall t\iff \Delta_2=(1-y)^2+4x-4\le0$$ and the first inequality give $$t^2+(1+y)t+x+1\ge0,\forall t\iff \Delta_1=(1+y)^2-4x-4\le0$$ ...


2

$\max_{1\leq i \leq N} x_i$ is the standard notation, and note that the symbol $||\cdot||:\mathbb{R}^n \rightarrow \mathbb{R}$ usually denotes a norm, which max is not.


2

You should use $\max x_i$ or $\max_i x_i$. It is not a norm, so you shouldn't use $\|x\|_\square$ or anything like that. Maybe you could define a notation like $(x)_{max}$, but I don't think there already is one.


2

Usually the triple bar notation is used for the subordinate norm for the linear transformation i.e. if $f: (E,||.||_E)\to (F,||.||_F)$ is a linear transformation then we definite the subordinate norm of $f$ by $$|||f|||=\sup_{x\in E\setminus\{0_E\}}\frac{||f(x)||_F}{||x||_E}$$


2

The constraint $\|\mathbf x\|_2^2 \leq \alpha \|\mathbf y\|_2^2$ is inactive when $\alpha$ is large enough so that the solution to the unconstrained problem is the solution to the constrained problem. Then, the unconstrained problem does not depend on $\alpha$.


2

There are no elements in $\Bbb F_p((t))$ with infinitely many negative powers of $t$; all of them are of the first form you described. (Indeed there can be no multiplicative structure on the set of infinite sums of the second form you described, since multiplication of them is ill-defined in general.)


2

Let $\left\{ \mathbf{x}^{n}\right\} $ be a Cauchy sequence in $\mathbb{R}^{k}$. Then for all $\epsilon>0$, there exists $N$ s.t. $$ \left\Vert \mathbf{x}^{n}-\mathbf{x}^{m}\right\Vert _{\infty}<\epsilon $$ for all $n,m>N$. This implies that $$ \left|x_{i}^{n}-x_{i}^{m}\right|<\epsilon $$ for each $i$. So each $\left\{ x_{i}^{n}\right\} $ is a ...


2

Assuming $v\neq 0$, note that $$ 2\|v\|\frac{d}{dt} \|v\| = \frac{d}{dt} \|v\|^2=\frac{d}{dt} v\cdot v=2v\cdot \dot\alpha. $$ It follows from the Cauchy-Schwarz inequality that $$ \frac{d}{dt}\|v\|\leq \|\dot \alpha\|. $$ If you do not assume $v\neq 0$, it may be that $\| v\|$ is not classically differentiable. Assuming that $v$ is once continuously ...


1

I think it is. Let $1<p<\infty$ be given and notice that the mapping $T$ from $W^{1,p}(\Omega)\to L^p(\Omega, R^{N+1})$ via $$ T[u]\to (u,\nabla u) $$ is isomorphic and closed. Together with the fact that $L^p(\Omega, R^{M})$ is uniformly convex for any $M\geq 1$, here we are interested in the case $M=N+1$, hence we know that $W^{1,p}$ is uniformly ...


1

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 ...


1

it is not true, say on the real line take $x_0=3$, $r=2$, $x=1.2$, then $\dfrac r 2 x-x_0= -1.8\not\in B(x_0,r)$. Hmm, edit, now the assumption says $||x||=1$. On the real line take $x_0=2.5$, $r=2$, $x=1$, then $\dfrac r 2 x-x_0= -1.5\not\in B(x_0,r)$.


1

Ah, I didn't realize that $X$ was required to be positive as well. Are you sure a clean solution exists? Since $BX$ is monotonic in all entries of $X$, dynamic programming can solve the problem in time pseudopolynomial in the magnitudes of the entries of $A$; this approach will only be practical for small $A$ however. Branch and bound codes like MIQPBB ...


1

The specific problem you have appears to be trivial for state-of-the-art MIQP solvers (i.e., branch and bound/cut). It is solved to 5-6 digits of accuracy in 0s. There might be smarter ways to solve the problem, but I reckon not much smarter, as it is a combinatorial problem by nature. Heuristics might work very well though, in case you don't care about ...


1

Let $$E_n(f)=a,\qquad E_n(g)=b$$ There exist two polynomials $p_1$ and $p_2$ such that $$\|f-p_1\|<a+\epsilon,\qquad \|g-p_2\|<b+\epsilon$$ so $$E_n(f+g)\le\|f+g-p_1-p_2\|\le a+b+2\epsilon$$ for all epsilon, so $$E_n(f+g)\le a+b=E_n(f)+E_n(g)$$


1

Given the dual quaternion defined by $z = (a+a_0\epsilon)+(b+b_0\epsilon)i+(c+c_0\epsilon)j+(d+d_0\epsilon)k$ $= (a+bi+cj+dk)+(a_0+b_0i+c_0j+d_0k)\epsilon$, for $a,a_0,b,b_0,c,c_0,d,d_0 \in \Bbb R$, $i,j,k$ defined by $i^2=j^2=k^2=ijk=-1$, and $\epsilon$ defined by $\epsilon \ne 0$ and $\epsilon^2 = 0$, the conjugate $\overline{z}$ is defined by : ...


1

There is a value of $\vec{x}$ for which $||\vec{y}+A\vec{x}||$ is minimized. Think of $\vec{y}$ as a vector in 3-space, $A\vec{x}$ is all the points in a plane through the origin, and $y+Ax$ is the set of points in a plane through the point $y$. There is one point in this plane closest to the origin. Call it $y+Ax_0$. As soon as $\alpha$ is large enough ...


1

@ ziutek , a matrix norm $||.||$ is defined on a space $M_{n,m}$. If $||.||$ is sub-multiplicative, then necessarily $m=n$ and $A$ cannot be rectangular. Moreover there is a big mistake in your line 5. Indeed if $\rho(BA)\leq 1$, then, we have only the following: for every $\epsilon>0$, there is an induced norm $N()$ s.t. $N(BA)\leq \rho(BA)+\epsilon$. ...


1

Obviously, the norm is at least what you anticipate by setting $f = e_n$ where $n$ almost realizes the supremum of $|\lambda_n - \lambda|^{-1}$. Conversely, write $f$ as $f = \sum_n c_n e_n$. Then $$\|(K - \lambda I)^{-1} f\|^2 = \sum_n |c_n|^2 |\lambda_n - \lambda|^{-2} \leq (\sup_n |\lambda_n - \lambda|^{-2}) (\sum_n |c_n|^2).$$ Taking the square root ...


1

No, it cannot be true. Take $A=B$ but $a\ne b$. Then $$ \|aA-bB\|_1 = |a-b| \|A\|_1 \not\le \max(a,b) \|A-B\|_1 = 0. $$


1

Not really. For any two matrices $A$ and $B$ and any $\epsilon>0$, put $T=\frac\epsilon{2\|A-B\|}I$. Then $\|TA-TB\|=\frac\epsilon2<\epsilon$. So you would be able to do this for any two matrices. If you require this to be true for any $\epsilon>0$, then this would imply $TA=TB$ which of course implies $A=B$. EDIT: The best bound we can do is ...


1

We can show a slightly different result, which gives a slightly stronger version of the statement in question when $t\geq 0$ with $\|\cdot\|=\|\cdot\|_{\infty}$. Let $$\|A\|_{\mathrm{max}}:=\max\limits_{i,j}|a_{ij}|$$ be the $\max$-norm of $A$ and $\|A-B\|_{\max}\leq t$. It is tempting to write $\|T(A-B)\|_{\max}\leq \|T\|_{\max}\|A-B\|_{\max}$, which is ...


1

One of the proofs is the following that uses quadratic function which I like: $0\leq \displaystyle \sum_{j=1}^n(a_{1j}-\lambda x_j)^2 = \displaystyle \sum_{j=1}^n a_{1j}^2 - 2\lambda\displaystyle \sum_{j=1}^n a_{1j}x_j + \lambda^2\displaystyle \sum_{j=1}^n x_j^2 = f(\lambda), \forall \lambda \in \mathbb{R} \Rightarrow \triangle' \leq 0 \Rightarrow ...


1

1) The map is positive, hence $\|tr \|=tr(I)=n$.



Only top voted, non community-wiki answers of a minimum length are eligible