most recent 30 from http://mathoverflow.net 2013-05-21T21:14:03Z http://mathoverflow.net/feeds/user/11870 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94435/how-to-bound-the-sup-norm-of-a-rademacher-process-or-equivalently-a-gaussian-proc wmmiao 2012-04-18T17:38:23Z 2012-09-06T08:43:59Z

<p>I want to know how to find an upper bound of the following expectation taken for both $t$ and $y$ as</p> <p>$$\mathbb{E}\sup_{x \in D} \left|\sum_{k=1}^n t_k x^T y_k\right|,$$ where $D$ is the set of vectors defined by $$D = ( x \in \mathbb{R}^m \mid 0\leq x_i \leq 1, \forall 1\leq i\leq m ),$$</p> <p>$\left(t_k\right)_{k=1}^n$ is the Rademacher sequence, that is, $t_1, \cdots, t_n$ are i.i.d. copies of a random variable $t$ taking values $\pm 1$ with $\mathbb{P}(t=1)=\mathbb{P}(t=-1)=1/2$, and $(y_k)$ are i.i.d. copies of a random vector $y \in \mathbb{R}^m$ taking values $e_1,\cdots,e_m$ with $\mathbb{P}(y = e_i)=p_i$. Here, $e_i$ denotes the vector from the standard basis with $i$-th component being 1 and the others being 0.</p> <p>I first get rid of the absolute value as \begin{align} &amp; \mathbb{E}\sup_x \left|\sum t_k x^T y_k\right| \leq \mathbb{E}_y\left(\sqrt{\frac{\pi}{2}} \mathbb{E}_s \sup_x\left| \sum s_k x^T y_k\right|\right) \\ \leq &amp; \sqrt{2\pi} \mathbb{E}_y\left(\mathbb{E}_s \sup_x\left(\sum s_k x^T y_k \right)\right) = \sqrt{2\pi} \mathbb{E} \sup_x\left(\sum s_k x^T y_k \right), \end{align} where $s_k$ are i.i.d copies of a standard normal random variable.</p> <p>Then, how to continue? My guess is that the upper bound seems to be of order $O(\sqrt{n})$. Is that correct? Thanks!</p>

http://mathoverflow.net/questions/100387/is-the-solution-of-this-linear-system-always-positive-definite wmmiao 2012-06-22T19:29:46Z 2012-06-22T19:29:46Z

<p>Let $P\in \mathbb{R}^{n\times r}$ be a submatrix (which consists of the first $r$ columns) of an arbitrary $n\times n$ orthogonal matrix ($1 &lt; r &lt; n$). Let $I_n$ denote the $n\times n$ identity matrix and $E_n$ denote the $n\times n$ matrix with all entries being $1$. Let $J_n := E_n -I_n$. Consider the following linear system $$P^T(J_n\circ PSP^T)P = I_{r},$$ where ''$\circ$'' denotes the Hadamard product.</p> <p>It can be shown that when $S$ is restricted to be an $r\times r$ symmetric matrix, this linear system always has a unique solution.</p> <p><strong>Question: Is the unique solution $S$ always positive definite?</strong></p> <hr> <p>FYI: Illustration of the uniqueness of the solution.</p> <p>Let $\text{vec}(\cdot)$ denote the vectorization operator by stacking the columns of a matrix into a single column and $\text{vech}(\cdot)$ denote the vectorization operator for symmetric matrices by stacking only diagonal and lower-diagonal entries column by column. Let ''$\otimes$'' denote the Kronecker product. The linear system when restricted to the symmetric matrix cone can be rewritten as $$[H_r(P\otimes P)^T \text{Diag}(\text{vec}(J_n))(P\otimes P) G_r] \text{vech}(S) = \text{vech}(I_r),$$ where $\text{Diag}(\text{vec}(J_n))$ is an $n^2 \times n^2$ diagonal matrix with $n^2-n$ nonzero diagonal entries $1$, $P\otimes P \in \mathbb{R}^{n^2 \times r^2}$ is of full-rank, $H_r \in \mathbb{R}^{r(r+1)/2\times r^2}$ and $G_r \in \mathbb{R}^{r^2\times r(r+1)/2}$ are full-rank matrices such that for any $r\times r$ symmetric matrix $X$, $$\text{vech}(X) = H_r\text{vec}(X), \quad \text{vec}(X) = G_r\text{vech}(X), \quad \forall \ r\times r \ \text{symmetric matrix} \ X.$$ Notice that $n^2-n\geq r^2$ for any $1 &lt; r &lt; n$. Since $P\otimes P$ is the first $r^2$ columns of an orthogonal matrix, $\text{Diag}(\text{vec}(J_n)) (P\otimes P)$ is of full rank and thus we obtain the uniqueness.</p>

http://mathoverflow.net/questions/98367/a-sum-of-eigenvalues wmmiao 2012-05-30T12:01:26Z 2012-05-30T12:54:48Z

<p>Let $X$ be an $n\times n$ symmetric matrix. Suppose $\lambda_1(X)\geq \lambda_2(X) \geq \cdots \geq \lambda_n(X)$ are eigenvalues of $X$. Let $r$ be any integer with $1\leq r\leq n$. It is well-known that $\sum_{i=1}^r \lambda_i(X)$ is convex. Now, my question is: Is the following function convex? $$\sum_{i=1}^r \max(0,\lambda_i(X))$$</p> <p>Thanks!</p>

http://mathoverflow.net/questions/97216/a-question-for-solutions-of-perturbed-linear-systems wmmiao 2012-05-17T12:32:03Z 2012-05-17T15:18:08Z

<p>Consider a linear system $$Ax=b\qquad (*)$$ and a sequence of perturbed linear systems $$(A+\delta A_n)x=b+\delta b_n. \qquad (n)$$ Suppose that all the linear systems are consistent (i.e., have solutions). </p> <p>My question is: Let $\overline{x}$ be a solution to $(*)$. Suppose that $\delta A_n \rightarrow 0$ and $\delta b_n \rightarrow 0$. Does there exist a sequence of solutions $\overline{x}_n$ such that each $\overline{x}_n$ is a solution to the linear system $(n)$, satisfying $\overline{x}_n \rightarrow \overline{x}$?</p> <p>A possible helpful result is that for any solution $x_n$ to the linear system $(n)$, there exists a solution $x$ to the linear system $(*)$ such that $$\frac{\|x_n - x\|}{\|x\|}\leq \frac{\|A^\sharp\|\|A\|}{1-\|A^\sharp\|\|\delta A_n\|}\left(\frac{\|\delta b_n\|}{\|b\|}+\frac{\|\delta A_n\|}{\|A\|}\right)\quad \text{if} \ \|A^\sharp\| \| \delta A_n\| &lt;1,$$ where $A^\sharp$ denotes the (weighted) Moore-Penrose inverse or the Drazin inverse. However, the existence of a solution in this result is for the linear system $(*)$ rather than the linear system $(n)$. The above result also holds if we replace $(x, x_n, A)$ with $(x_n, x, A+\delta A_n)$ respectively by considering the $( * )$ as a perturbation of $(n)$. However, if so, $x_n$ and $(A+\delta A_n)^\sharp$ are not guaranteed to be bounded and thus we cannot have a upper bound of $\|x_n-x\|$ tending to $0$. (Correct?) </p> <p>Anyone can help? Thank you!</p>

http://mathoverflow.net/questions/94435/how-to-bound-the-sup-norm-of-a-rademacher-process-or-equivalently-a-gaussian-proc/94441#94441 wmmiao 2012-04-18T18:33:44Z 2012-04-18T19:01:16Z

<p>Is the following correct?</p> <p>Notice that $t$ and $y$ are independent, we have $\mathbb{E} = \mathbb{E}_y\mathbb{E}_t$. Then we focus on the inner expectation $\mathbb{E}_t$ for some fixed $y_1=e_{(1)},\cdots, y_n=e_{(n)}$. </p> <p>$$\mathbb{E} \sup_{x\in D}\left|\sum_{k=1}^n t_k x^T y_k\right| = \mathbb{E} \sup_{x\in D} \left|\sum_{k=1}^n t_kx_{(k)} \right|\leq \mathbb{E}\left|\sum_{k=1}^n t_k \right|\leq \sqrt{\frac{\pi}{2n}} \quad ???$$</p> <p>The above upper bound does not depend on $y$. Thus, it is also an upper bound for the expectation of both $y$ and $t$. Is this correct?</p>

http://mathoverflow.net/questions/66361/an-inequality-on-concave-functions wmmiao 2011-05-29T13:13:44Z 2011-07-23T22:28:24Z

<p>Could somebody help me to answer the following question?</p> <p>Let $f:R_+ \rightarrow R_+$ be a nonindentically zero, nondecreasing, continuous, concave function with $f(0)=0$. Do we have that for any $s,t \in [0,1]$,</p> <p>$$f(x)f(stx)\leq f(sx)f(tx), \quad \forall x \geq 0.$$</p> <p>or equivalently, do we have that for any $t\in (0,1)$, $\frac{f(x)}{f(tx)}$ is nonincreasing on $x >0$.</p> <p>Thanks!</p>

http://mathoverflow.net/questions/66361/an-inequality-on-concave-functions/66369#66369 wmmiao 2011-05-29T15:09:16Z 2011-05-29T15:09:16Z

<p>I just got the proof by myself.</p> <p>Without loss of generality, we assume $f$ is continuously differentiable. Otherwise, one can use the smoothing technique.</p> <p>Notice that $$\left(\frac{f(x)}{f(tx)}\right)' = \frac{f'(x)f(tx)-tf(x)f'(tx)}{f^2(tx)}.$$ We only need to show $$\frac{f'(x)}{f(x)} \leq \frac{tf'(tx)}{f(tx)},$$ which is just $$[(\log\circ f)(x)]'\leq [(\log \circ f)(tx)]'.$$ Thus, we only need to show the composition $\log\circ f$ is concave. This is true since $f$ is concave and positive for $x>0$. Thus we complete the proof.</p>

http://mathoverflow.net/questions/50576/a-question-about-the-generalized-lidskii-wielandt-inequality-for-matrices-proved wmmiao 2010-12-28T16:53:13Z 2010-12-28T20:25:44Z

<p>In 1971, Thomson and Freede generalized the Lidskii-Wielandt inequalites as follows (version for singular values)</p> <p>Let $A$, $B$ be $n\times n$ Hermitian matrices. Suppose $\alpha_1\geq \alpha_2 \geq \cdots \geq \alpha_n, \beta_1\geq \beta_2 \geq \cdots \geq \beta_n, \gamma_1\geq \gamma_2 \geq \cdots \geq_n$ are the singular values of $A$,$B$ and $A+B$ respectively. Let $i_1,\cdots,i_m$ and $j_1, \cdots,j_m$ be integers such that $i_m+j_m\leq m+n$ and $1 \leq i_1 &lt; \cdots &lt; i_m \leq n, 1 \leq j_1&lt; \cdots &lt; j_m \leq n$. Then one has $$\sum_{s=1}^m \gamma_{i_s+j_s-s}\leq \sum_{s=1}^m \alpha_{i_s} +\sum_{s=1}^m \beta_{j_s}.$$ </p> <p>Now, my question is : if we define two new vectors $\hat{\gamma}$ and $\hat{\alpha}$ by $\hat{\gamma}_i=\max(\gamma_i,\alpha_i)$ and $\hat{\alpha}_i=\min(\gamma_i,\alpha_i)$ for $i=1,\cdots,n$, does the the following inequality which is similar to the above one still hold? $$\sum_{s=1}^m \hat{\gamma}_{i_s+j_s-s}\leq \sum_{s=1}^m \hat{\alpha}_{i_s}+\sum_{s=1}^m \beta_{j_s}.$$</p> <p>This is true for the simpler case by considering the Lidskii-Wielandt inequality $$\sum_{s=1}^m (\hat{\gamma}_{i_s} - \hat{\alpha}_{i_s}) = \sum_{s=1}^m \vert\gamma_{i_s}-\alpha_{i_s}\vert \leq \sum_{s=1}^m \beta_s.$$ For the general case, I use the Matlab to generate many random matrices to check and it seems that it is correct. However, I have no idea about how to prove or disprove it. Can anyone help me?</p>

http://mathoverflow.net/questions/100387/is-the-solution-of-this-linear-system-always-positive-definite 2012-06-22T21:02:19Z 2012-06-22T21:02:19Z

I see. But if so, I want to point out that the left-hand side is not $J_r\circ S$.

http://mathoverflow.net/questions/100387/is-the-solution-of-this-linear-system-always-positive-definite 2012-06-22T20:41:37Z 2012-06-22T20:41:37Z

I believe the answer of the question is true based on random generated numerical tests. Numerical tests also show that it should be true if the term $I_r$ on the right-hand side is replaced by any diagonal matrix with positive diagonal entries.

http://mathoverflow.net/questions/100387/is-the-solution-of-this-linear-system-always-positive-definite 2012-06-22T20:36:27Z 2012-06-22T20:36:27Z

Assumption: $1&lt;r&lt;n$. So $P$ cannot be the identity matrix. If so, we cannot have $n^2-n\geq r^2$ in the last line but two.

http://mathoverflow.net/questions/98367/a-sum-of-eigenvalues/98371#98371 2012-05-30T12:42:57Z 2012-05-30T12:42:57Z

Yes, your idea is correct. But the reason should be revised to be $$f(X) = \max\{0,\sum_{i=1}^1 \lambda_i(X), \cdots, \sum_{i=1}^r \lambda_i(X)\}.$$

http://mathoverflow.net/questions/98367/a-sum-of-eigenvalues/98369#98369 2012-05-30T12:24:35Z 2012-05-30T12:24:35Z

Yes, assume to be real. But what we want to prove is for any 0≤α≤1, $$\alpha \sum_{i=1}^r \max(0, \lambda_i(X))+(1-\alpha)\sum_{i=1}^r \max(0,\lambda_i(Y)) \leq \sum_{i=1}^r \max(0,\lambda_i(\alpha X+(1-\alpha)Y)). $$It is not trivial.

http://mathoverflow.net/questions/94435/how-to-bound-the-sup-norm-of-a-rademacher-process-or-equivalently-a-gaussian-proc/94441#94441 2012-04-18T19:25:36Z 2012-04-18T19:25:36Z

The first inequality is wrong... it seems that it should be of order n.

http://mathoverflow.net/questions/94435/how-to-bound-the-sup-norm-of-a-rademacher-process-or-equivalently-a-gaussian-proc/94446#94446 2012-04-18T19:00:32Z 2012-04-18T19:00:32Z

At the beginning, I also think so. However, I did not find a mistake in my answer provided below... So I doubt..

http://mathoverflow.net/questions/94435/how-to-bound-the-sup-norm-of-a-rademacher-process-or-equivalently-a-gaussian-proc 2012-04-18T18:59:16Z 2012-04-18T18:59:16Z

Yes, thanks for pointing

http://mathoverflow.net/questions/94435/how-to-bound-the-sup-norm-of-a-rademacher-process-or-equivalently-a-gaussian-proc 2012-04-18T18:39:43Z 2012-04-18T18:39:43Z

where is $\varepsilon$?

http://mathoverflow.net/questions/66361/an-inequality-on-concave-functions/66369#66369 2011-05-31T12:43:22Z 2011-05-31T12:43:22Z

I just found that this proof is wrong since $[(\log\circ f)(tx)]'$ is different from $(\log\circ f)'(tx)$. So, anyone can help? Thanks!

http://mathoverflow.net/questions/66361/an-inequality-on-concave-functions/66387#66387 2011-05-30T14:26:38Z 2011-05-30T14:26:38Z

The positivity of $f$ is just for the domain of the $\log$ function.

http://mathoverflow.net/questions/50576/a-question-about-the-generalized-lidskii-wielandt-inequality-for-matrices-proved 2010-12-29T07:32:41Z 2010-12-29T07:32:41Z

Yes, such the inequality doesn't hold for eigenvalues. You can consider a well-know result, that is $\vert \sigma(X)-\sigma(Y) \vert$ is weakly majorized by $\sigma(X-Y)$, wherer $\sigma(X)$ deontes the vector of singular values of $X$ arranged in the decreasing order. This inequality just means that $\sigma_i(X)$ and $\simga_i(Y)$ can be exchanged in the inequality due to the absolute value. This is just a special case of the Likskii-Wielandt inequality for singular values. My question is about whether the generalized Likskii-Widlandt still have such &quot;exchange&quot; property.