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

- 142k

19
votes

### When do people actually use the maximum entropy distribution?

Many classically important probability distributions are maximum entropy distributions for suitable constraints, including the normal distribution, exponential distribution, and Poisson distribution. ...

- 45k

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,010

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,069

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

- 29.2k

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

- 11.8k

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

- 54.3k

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

9
votes

Accepted

### When do people actually use the maximum entropy distribution?

In finance, finding risk neutral probabilities can be done via max-entropy methods.
In short, you observe prices $p_i$ of a finite number of instruments $\phi_i$, and you seek a probability measure $...

- 206

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

- 54.3k

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

- 38.5k

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,425

8
votes

### When do people actually use the maximum entropy distribution?

I have found this book a useful reference:
Maximum-entropy Models in Science and Engineering
It may contain some pointers to applied work that you will find convincing (I don't have it on me right ...

- 2,691

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

- 85.1k

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,563

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

7
votes

### Convex Sets and Nearest Neighbors

A nonempty set $S$ in a normed linear space $X$ is called a Chebyshev set if for each $u \in X$ there is exactly one nearest point in $S$ to $u$ (i.e., for a Chebyshev set, nearest points always exist,...

- 28k

7
votes

Accepted

### Lower bound for spectral radius on $\operatorname{GL}(n,\mathbb{Z})$

Every monic integer polynomial $f(x) \in \mathbb{Z}[x]$ of degree $n$ is the characteristic polynomial of an $n \times n$ matrix, namely its companion matrix. The companion matrix is invertible iff ...

- 110k

7
votes

Accepted

### Maximizing Frobenius Norm of Commutator (an opposite Procrustes problem)

Unless I'm mistaken, the following argument provides a solution.
Since the Frobenius norm is orthogonally invariant we can assume without loss of generality that $S$ is diagonal. I'll write $Q$ ...

- 28k

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,844

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,182

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

- 155k

7
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,129

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,144

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

- 28k

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

- 32.5k

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

- 171

6
votes

Accepted

### Convex Sets and Nearest Neighbors

This is the celebrated Chebyshev problem. The answer is positive in $\mathbb{R}^n$, and still open in the Hilbert space.

- 52.2k

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

#### Related Tags

convex-optimization × 733oc.optimization-and-control × 191

nonlinear-optimization × 166

convex-analysis × 135

linear-algebra × 112

linear-programming × 85

fa.functional-analysis × 78

convexity × 65

real-analysis × 54

convex-geometry × 54

global-optimization × 52

pr.probability × 41

reference-request × 40

matrices × 37

convex-polytopes × 36

semidefinite-programming × 32

na.numerical-analysis × 24

inequalities × 22

ca.classical-analysis-and-odes × 20

st.statistics × 19

probability-distributions × 18

combinatorial-optimization × 18

mg.metric-geometry × 17

duality × 17

computational-complexity × 16