21
votes
Is There an Induction-Free Proof of the 'Be The Leader' Lemma?
Is the following any clearer? (Read the subscripts carefully!)
$$\begin{array}{ll}
f_1(y_1) + f_2(y_2) + f_3(y_3) + \cdots + f_n(y_n) &\leq \\
f_1(y_2) + f_2(y_2) + f_3(y_3) + \cdots + f_n(...
- 156k
17
votes
How to make a sandwich from just one piece of bread?
This won't be a complete answer to Q2, but something of a starting point, at least for all two-dimensional convex $P$. Assuming for simplicity that the area of $P$ is 1, $P$ contains a parallelogram ...
- 7,276
14
votes
Current state of the Komlos conjecture on vector balancing
As far as I know, the state of the art is that one can actually achieve $K=K(n)=O(\log^{\frac{1}{2}} n)$ independent of the dimension $d$. Moreover, one can actually find the weights $w_i$ via an ...
- 32.1k
11
votes
Accepted
Why are $\Gamma_0$ functions called this
I think Carlo Beenakker digged up the right reference for the notation of the set, but I think more can be said.
First, there is some meaning for the subscript $0$ which can be found in the same ...
- 12.7k
11
votes
How to make a sandwich from just one piece of bread?
Restricting to the case where $P$ is triangular, if the angles of the triangle are $A$, $B$, $C$ and you fold the triangle along the bisector to the angle $C$, then assuming wlog that $A<B$, you ...
- 2,902
10
votes
Accepted
Current state of the Komlos conjecture on vector balancing
For fixed $d$, one can actually achieve a bound independent of $n$. More precisely, $K=K(d)=O(\sqrt{d})$ is fine, uniformly in $n$.
Proof : the unit ball of $\mathbb{R}^d$ can be covered by $2C^d$ ...
- 7,239
10
votes
Accepted
property of convex functions
Anyway, If you know a 5 line proof for the first inequality please share it with us
OK, here goes.
Assume that $\inf_P f=-1$ and that it is (nearly) attained at the origin. Let $K=\{x\in P: f(x)\le ...
- 61.9k
10
votes
Accepted
Closedness of linear image of positive L1 functions
Take $\mathcal X = L^1(\Omega,\mu)$ where $\Omega = \{1,2,3,\dots\}$ and measure $\mu(\{k\}) = p_k$ with $p_k > 0$,
$\sum p_k = 1$. The norm in $\mathcal X$ is
$$
\|f\|_{\mathcal X} = \sum_k |f(k)|...
- 41.1k
10
votes
Is the pseudoinverse the same as least squares with regularization?
Yes, they are connected.
The first problem is a special case of the second when $\lambda=0$, if the first problem has a unique solution (i.e., $\ker A = 0$), or if the second is also formulated as a ...
- 20.2k
10
votes
Accepted
Is the pseudoinverse the same as least squares with regularization?
Here's one way to see this directly. I will assume that $A$ is $m \times n$. Let
$$ A = U \Sigma V^T$$
be the SVD for A. Recall that the regularized solution to the least squares problem $Ax = b$ is ...
- 2,607
10
votes
Accepted
Optimal polynomial approximation of rational function $\frac{1}{1-x}$
This problem has an exact solution, written in the book
N. I. Akhiezer, Theory of approximation. Dover Publications, Inc., New York, 1992, Chap II section 37.
The error is
$$\frac{(1-\sqrt{1-\rho^2})^...
- 91.8k
9
votes
Accepted
Is KL divergence $D(P||Q)$ strongly convex over $P$ in infinite dimension
$\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\ep}{\varepsilon}$
Take any probability measures $P_0,P_1$ absolutely continuous with respect (w.r.) to $Q$.
We shall prove the ...
- 128k
8
votes
An intuition for three different types of subgradients (proximal, regular, limiting)
This might not be a satisfying answer, but this is how I personally deal with this issue (at least in the topic of optimization).
I think these concepts are not made for actually computing them but ...
- 191
8
votes
Bounding the spectral gap of a simple symmetric matrix
Let $x$ be the smallest nonzero eigenvalue of $A$. It is the reciprocal of the largest root of
$$f(t)=-\det(t(D-aa^\top)-I),$$
where $D$ is the diagonal matrix. By the matrix determinant lemma,
\begin{...
- 1,593
8
votes
Is the pseudoinverse the same as least squares with regularization?
TL;DR : Yes, the two problems are equivalent in the limit $\lambda \rightarrow 0$ !
One freely available reference is the following (excellent in my opinion) review paper : https://arxiv.org/abs/1110....
- 297
8
votes
Is this geometrically-defined minimum an algebraic number?
By Carathéodory's theorem, if the origin in $\mathbb{R}^{32}$ is contained in the convex hull of the set
$$
X_c = \{\,(x, y, x^2 - 1, \ldots, y^8 - 14) \mid -2 \le x, y \le 2, x + y \ge c\,\}
$$
then ...
- 25.2k
7
votes
Why are $\Gamma_0$ functions called this
It seems the notation $\Gamma_0$ was introduced by Jean-Jacques Moreau in Proximité et dualité dans un espace Hilbertien (1965), as a generalisation of the notion of projection onto a convex domain (...
- 188k
7
votes
Accepted
Optimization problem with determinant as objective
One can verify that $U_{A}=U_{S}$ as follows. Note that $$\det(U_{A}\Sigma_{A}V_{A}^{T}+U_{S}\Sigma_{S}V_{S}^{T})=\det(\Sigma_{A}+U_{A}^{-1}U_{S}\Sigma_{S}V_{S}^{T}V_{A}^{-T})$$
Let $Y=U_{A}^{-1}U_{S}...
- 3,209
7
votes
Accepted
Inf of Jensen's inequality
Jensen's inequality $\int c(f)\,d\mu \ge c(\int f\,d\mu)$ is always equality when $f$ is constant, so you know that taking $dz/dt$ constant would saturate it. That means $z(t)$ has to be linear, and ...
- 29.7k
7
votes
Exactness of the semidefinite programming (SDP) relaxation of maximum cut (Max-Cut)
This question was studied somewhat in the early '90s (before Goemans--Williamson, in fact; note that it was Delorme and Poljak who first gave a poly-time SDP algorithm for Max-Cut, conjecturing that ...
- 6,694
7
votes
Accepted
How to apply Hahn-Banach to the convex hull?
To solve the problem you mention at the end you can argue in this way:
$$
\min_{m \in \mathrm{conv} (M)} \|m\|_{2}=\min_{m \in \mathrm{conv} (M)} \max_{\|\alpha\|_{2}\leq 1} \langle \alpha, m\rangle = ...
- 3,946
7
votes
Accepted
Nondifferentiable convex function whose subdifferential admits a continuous selection
The answer is no.
See Rockafellar's Convex Analysis, part V.
First, let $D$ be the set of points where $F$ is differentiable. Theorem 25.5 proves that $D$ is dense in the interior of the domain of $F$,...
- 39k
7
votes
Accepted
Reference request: importance of Lipschitz continuity
In Mathematical/High Dimensional Statistics:
One fairly amazing result is for $X=(X_1,\dots,X_n)$ where the coordinates are i.i.d. standard Gaussians, and $f:R^n \to R$ a $L$-Lipschitz function (w.r.t....
- 206
7
votes
Accepted
Maximizing trace subject to two equality constraints
If ${\rm rank} \, X>1$, there exists a two-dimensional space $\mathcal{L}$ such that the restriction of $X$ to $\mathcal{L}$ is positive definite. The space of Hermitian operators, which vanish on ...
- 109k
6
votes
Abstract treatment of multivariate calculus relevant for optimization
Optimization is also done in Banach spaces - don't know if this is abstract enough, but, see, e.g.
Barbu, Viorel, and Teodor Precupanu. Convexity and optimization in Banach spaces. Springer Science ...
- 12.7k
6
votes
Accepted
Is the solution of this optimization problem always positive semidefinite?
No, it is not always attained at a positive semidefinite matrix. The simplest example I have been able to find to demonstrate this is as follows:
\begin{align*}
U = \{ (1,0), (0,1), \tfrac{1}{\...
- 6,351
6
votes
Only top scored, non community-wiki answers of a minimum length are eligible