DL, the new Bohr model: The thoughts of an irreducible DL troll

In the dawn of the 20th century, most physicists thought Physics had been solved! Thusly, chicken feasts with exquisite wine were organized in labs all around the globe. Then it turned out the Bohr model had serious gaps, and suddenly the party was over, and all lights were put out. DL is the new Bohr model (assuming it is a model at all...), and ICLR2016 looks like a chicken feast :p

Random thoughts on the Lasso (to be continued...)

For any $n$-by-$p$ matrix $X$ (with non-zero rows), consider the following objects
$$\mathcal P_X := \{z \in \mathbb R^n | \|X^Tz\|_\infty \le 1\},\; D_X := \text{diag}(\|X_1\|_\infty,\ldots, \|X_n\|_\infty),\; Z_{D_X} := D_X^{-1}\mathbb B_1,$$
where $\mathbb B_1$ is the unit-ball for the $\ell_1$-norm.  Note that $Z_{D_X} \subseteq \mathcal P_X$.

Given a closed convex set $K \subseteq \mathbb R^n$, we've defined the euclidean projection
$$\text{proj}_K(a) := \text{the unique point of }K\text{ minimizing distance from }a \text{ to } K.$$
It's not (too) hard prove that $0 \le QP \le QA$.

What more (of geometric taste) can be said about the picture ?

$\frac{1}{2}\|.\|^2$ is the only self-dual function on a Hilbert space $X$!

Let $X$ be a Hibert space, $x \mapsto \|x\| := \sqrt{x^Tx}$ be the euclidean norm on $X$, and $f:X \rightarrow (-\infty,+\infty]$ an extended real-valued function. Define the convex conjugate of $f$, denoted $f^*$, by
$$f^*(y) := \sup_{x \in X}x^Ty - f(x), \; \forall y \in X.$$
Note that $f^*$ is always convex l.s.c (being the supremum of affine functions) without any assumptions whatsoever on $f$.

Question: When do we have $f^* = f$ ? Checkout the answer here.

Paper accepted at ICASSP 2016!

Our math paper entitled: "LOCAL Q-LINEAR CONVERGENCE AND FINITE-TIME ACTIVE SET IDENTIFICATION OF ADMM ON A CLASS OF PENALIZED REGRESSION PROBLEMS" has been accepted for the ICASSP 2016 signal-processing conference (the largest in the world). The conference will be held at the shicc (Shanghai Convention Center).

Author manuscript available upon demand.

Exact minimization of the linearly perturbed distance of a point to a closed convex set

Let $a, b \in \mathbb R^n$, and $C$ be a nonempty closed convex subset of $\mathbb{R}^n$ with $a \not \in C$. Consider the problem $$\text{minimize }\|x-a\| + b^Tx\text{ subject to } x \in C.$$ The case $b = 0$ corresponds to the well-known problem of projecting the point $a$ onto $C$. This problem can be easy or difficult, depending on the geometry of $C$ (for example, the latter problem is rather easy if $C$ is a diamond-shaped polyhedron, or an oval). However the perturbative case $b \ne 0$ is completely non-trivial and must be treated rather carefully. That notwithstanding, we show here that the case $\|b\| < 1$ is essentially equivalennt to the non-perturbative case $b = 0$.

Graph-Net vrs TV-L1: structure in regression coefficients

See conference paper for more theory on these multi-variate decoding / recovery models in brain science. Implementation to appear in next release of nilearn.

On the unreasonable effectiveness of Friedrichs angles: rates of convergence of powers of some weird operators

Statement of the problem

Let $d$ and $c$ be positive integers and $q = dc$. Let $G$ be a $q$-by-$q$ positive semi-definite real matrix with eigenvalues all $\le 1$, and define the $q$-by-$2q$ matrix $A = [G\hspace{1em}\mathrm{I}_q - G]$, where $\text{I}_q$ is the $q$-by-$q$ identity matrix. Now, given a scalar $\kappa > 0$ and $d$ vectors $X_1, X_2, \ldots, X_d \in \mathbb{R}^c$, with $\|X_j\| \ne \kappa \; \forall j$, consider the $q$-by-$q$ block-diagonal matrix $D$ whose $j$th block, a $c$-by-$c$ matrix, is given by \begin{equation} D_j = \begin{cases}\text{I}_c - \frac{\kappa}{\|X_j\|}\text{proj}_{\langle X_j \rangle^\perp}, &\mbox{ if } \|X_j\| > \kappa,\\ 0, &\mbox{ otherwise,}\end{cases} \end{equation} where $\text{proj}_{\langle X_j \rangle^\perp} = \mathrm{I}_c - \mathrm{proj}_{\langle X_j\rangle} = \mathrm{I}_c - \frac{1}{\|X_j\|^2}X_jX_j^T$ is the projection onto the orthogonal complement of the $1$-dimensional subspace of $\mathbb{R}^c$ spanned by the vector $X_j$. Finally define the $2q$-by-$q$ matrix $B = [D\hspace{1em}\mathrm{I}_q-D]^T$. For example, if $c=1$, then each $D_j \in \{{0,1}\}$, a bit indicating whether $|X_j| > \kappa$, and $D$ is a diagonal matrix with $0$s and $1$s accordingly. Now define the $2q$-by-$2q$ matrix $F := BA$ (Or $F := AB$. To see this equivalence, note that $(BA)^{n+1} = B(AB)^nA$, for all $n \in \mathbb{N}$. Thus to study the "convergence" of $((BA)^n)_{n \in \mathbb{N}}$, it suffices to study the convergence of $((AB)^n)_{n \in \mathbb{N}}$. In fact, if $(AB)^n \rightarrow C$, then $(BA)^n \rightarrow BCA$.).

Ultimately, I'm interested in the rate of convergence (in the sense of Definition 2.1 of this paper) of the sequence of matrix powers $(F^n)_{n\in\mathbb{N}}$. I can easily bound the spectral norm $r(F) \le \|F\| \le \|A\| \le 1$, but this turns out to be not very useful in my situation (e.g $\|A\|$ can be $1$). If I can compute the eigenvalues of $F$ (e.g in terms of the eigenvalues of $G$), then there is a fair chance I can apply the results of this paper to get rates of convergence for the aforementioned sequence.

Question

Can one relate (via a formula, for example) the eigenvalues of $F$ in terms of the eigenvalues of $G$ ? How fast does iterating $AB$ or $BA$ converge ?

Partial solution for limiting case when $G$ is the projection onto a subspace

In my initial problem, $G$ is a function of a scalar parameter, and after careful inspection, it turns out that in the limit as this parameter goes to infinity, $G$ becomes the projection operator onto a subspace of $\mathbb{R}^q$, i.e $G = \mathrm{proj}_{\text{Im }K} = K(K^TK)^{-1}K^T$ for some full column-rank $q$-by-$p$ matrix $K$ (with $p \le q$). If in addition $c=1$, then $D$ too is a projection (precisely, it is a diagonal matrix with only $0$s and $1$s, as already explained further above) and one computes \begin{eqnarray} \begin{split} F &= AB = [G\hspace{1em}\mathrm{I}_q - G][D\hspace{1em}\mathrm{I}_q - D]^T = GD + (\mathrm{I}_q - G)(\mathrm{I}_q - D)\\ &= \mathrm{proj}_U\mathrm{proj}_V + \mathrm{proj}_{U^\perp}\mathrm{proj}_{V^\perp}, \end{split} \end{eqnarray} where $U := \text{Im }K$, and $V := \text{Im }D$ (note that ${U^\perp} = \text{ker }K^T$ and ${V^\perp} = \text{ker }D^T$). It then suffices to invoke Theorem 3.10 of this [paper][2], with $\mu = 1 \in [0, 2)$ to obtain that the sequence of matrix powers $(F^n)_{n \in \mathbb{N}}$ has the optimal rate of convergence $\gamma = \cos{\theta_F}(U, V) \in [0, 1)$, the cosine of the the *Friedrichs angle* $\theta_F(U, V) \in [0,\pi/2]$ between $U$ and $V$ defined by: \begin{equation} \cos{\theta_F}(U, V) := \sup\{\langle u, v \rangle | u \in U \cap (U \cap V)^\perp, \|u\| \le 1, v \in V \cap (U \cap V)^\perp, \|v\| \le 1 \}. \end{equation}

Final words

As a pathological example, if $K$ (resp. $D$) is invertible, then $F = \mathrm{proj}_U$ (resp. $F = \mathrm{proj}_V$), and so $\cos{\theta_F}(U, V) = 0$. Consequently, $(F^n)_{n \in \mathbb{N}}$ convergences exponentially fast (in fact, in $1$ iteration!) to $F$.