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(...
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 ...
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) ...
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 ...
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 $...
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 ...
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 ...
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....
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 ...
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 ...
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, \...
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 (...
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 ...
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