From c39e48798659133abcb9bfe7b7c407b940b73c1a Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sun, 23 Nov 2014 11:19:36 -0500
Subject: Re-add formulation of the ML problem

---
 notes/formalisation.tex | 25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)

(limited to 'notes/formalisation.tex')

diff --git a/notes/formalisation.tex b/notes/formalisation.tex
index bdd6aab..00eb891 100644
--- a/notes/formalisation.tex
+++ b/notes/formalisation.tex
@@ -154,6 +154,31 @@ $$\vec w\sim B(1 - e^{M \theta_{*,i}})$$
 
 where the operation $f: \vec v \rightarrow 1 - e^{\vec v}$ is done element-wise and $B(\vec p)$ is a vector whose entries are bernoulli variables of parameter the entries of $\vec p$.
 
+\subsection{Maximum likelihood problem}
+
+The maximum likelihood problem takes the following form:
+\begin{displaymath}
+    \begin{split}
+        \max_\theta &\sum_{k,t}\left(b_{k,t}\log\left(1-\exp\inprod{A_k^t, \theta}\right)
+        + (1-b_{k,t})\log\exp\inprod{A_k^t,\theta}\right)\\
+    \text{s.t. }& \|\theta\|_1 \leq k
+    \end{split}
+\end{displaymath}
+which we can rewrite as:
+\begin{displaymath}
+    \begin{split}
+        \max_\theta &\sum_{k,t}b_{k,t}\log\left(\exp\left(-\inprod{A_k^t, \theta}\right)-1\right)
+        + \sum_{k,t}\inprod{A_k^t,\theta}\\
+    \text{s.t. }& \|\theta\|_1 \leq k
+    \end{split}
+\end{displaymath}
+In this form it is easy to see that this is a convex program: the objective
+function is the sum of a linear function and a concave function.
+
+\paragraph{Questions} to check: is the program also convex in the $p_{j,i}$'s?
+What is the theory of sparse recovery for maximum likelihood problems? (TO DO:
+read about Bregman divergence, I think it could be related).
+
 \subsection{Results under strong assumptions}
 
 What can we hope to have etc. (If M has full column rank or if same sets S occur frequently).
-- 
cgit v1.2.3-70-g09d2

