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(...
- 148k
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,270
14
votes
More general than semidefinite program?
There is the concept of hyperbolic programming, introduced in the 90's by Osman Güler:
O. Güler, Hyperbolic Polynomials and Interior Point Methods for Convex Programming, Math. Oper. Res. 22 (1997) ...
- 6,324
13
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 ...
- 30.4k
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.1k
10
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,842
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 ...
- 57.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)|...
- 39.9k
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 ...
- 18.9k
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})^...
- 86.4k
9
votes
Minimize sum of $\ell_2$ norm and linear combination, on simplex
I would try to approach your original problem a bit differently. Note that $|x-a|\le \frac 12(r|x-a|^2+r^{-1})$ and the equality is attained for $r=|x-a|^{-1}$. Thus,
$$
\min_x[|x-a|+\langle b,x\...
- 57.9k
9
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,169
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 ...
- 106k
9
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,495
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,573
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....
- 199
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 ...
- 24.5k
7
votes
Accepted
Nuclear norm (convex) minimization with complex-valued matrices?
Yes, the same approach can be used for complex matrices, with the constraint becoming
$\left[ \begin{array}{rr}
W_{1} & X \\
X^{H} & W_{2} \\
\end{array}
\right] \succeq 0
$
Here, the ...
- 3,874
7
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 ...
- 181
7
votes
Accepted
Finding Toeplitz matrix nearest to a given matrix
The set of $n \times n$ symmetric Toeplitz matrices is
$$\left\{ x_1 \mathrm M_1 + x_2 \mathrm M_2 + \cdots + x_n \mathrm M_n \mid x_1, x_2, \dots, x_n \in \mathbb R \right\}$$
where $\mathrm M_1, \...
- 2,226
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 (...
- 169k
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,147
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 ...
- 28.6k
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,671
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$,...
- 34.6k
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....
- 186
6
votes
Complexity of convex quadratically constrained quadratic programming (QCQP)
Convex quadratically constrained quadratic programming (QCQP) can be reduced to semidefinite programming (SDP). Suppose that we are given the following convex QCQP in $\mathrm x \in \mathbb R^n$
$$\...
- 2,226
6
votes
Accepted
L-infinity-norm regularized proximity problem
This is indeed a classic problem. Recall the more general problem of computing the prox operator of an lsc convex function $f$, i.e.,
\begin{equation*}
\text{prox}_f(y) := \operatorname{argmin}\quad \...
- 28.2k
6
votes
algorithm for finding the minimizer of a almost convex function
How abou trying to apply the Golden Search algorithm?
- 332
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}{\...
- 5,463
Only top scored, non community-wiki answers of a minimum length are eligible