Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need to find $x$ that minimizes the cost function $\|y-Ax\|_p$ when $p$ is close to $0$, subject to the constraint $\|x\|_2=1$ where $x$ and $y$ are vectors in $\mathbb{R}^n$ and $A$ is an $n\times n$ matrix of full rank such that $A^TA$ is diagonal with strictly positive entries and $\operatorname{Tr}(A^TA)=N$. The matrix $A$ and the vector $y$ are both known. The elements of $A$ are in $\mathbb{R}$. Do note that $A$ itself is not diagonal. Specifically (if it helps), $A=\begin{pmatrix} B& C\\ -C& B \end{pmatrix}$ where $B$ and $C$ are of size $n/2 \times n/2$ and are both symmetric matrices.

The problem is non-convex. Any thoughts on solving the expression with $A$ as an identity or diagonal matrix are more than welcome as well

The notation $\|z\|_p$ highlights the $L_p$ norm and is $\|z\|_p=\sum|z_i|^p$ where $z_i$ are the elements of $z$. For $p<1$, $\|\cdot\|_p$ is not a norm in the actual definition of the word as it defies the triangle inequality.

share|cite|improve this question

I am not sure if we can comment about the limiting behaviour. But we can certainly say something about what happens at the limit $p=0$.

At $p=0$, you are trying to minimizing the number of non-zero entries in the vector $e=y-Ax$. Thus, the objective function takes the values in the set $\{0,1,2,\dots,n\}$. The ideal minimum is zero, i.e. when $y=Ax$ and the maximum is $n$ which happens when none of the entries of $e$ are zeros, which means $y_i\neq [Ax]_i,~\forall i$ ($i^{th}$entry). I will try to approach it in a case by case manner.

Consider the case $A=I$. At the limit $p=0$, You are trying to minimize the $l_0$ norm (i.e. number of non-zero entries) in the difference vector $e=y-x$. But you also have the additional constraint that $||x||^2_2=1$. If $y$ was unit norm, then $x=y$ is the optimal solution. If it is not, then you have to zero out the entries of $y$ as much as possible, as your objective is to decrease the number of non-zero entries. The obvious solution (though a rigorous proof escapes me) is to zero out all smallest entries (in absolute sense) of $y$ such that their squared sum is less than or equal to 1. So, you zero out maximum number of non-zero entries.

Consider the case $A=D$ where $D$ is some diagonal matrix. Define $z=Dx$. So you have to zero out the entries of the vector $e=y-z$. Let us assume all diagonal entries of $D$ are non-zero. Now comes an important observation. For any vector $r$, the $l_o$ norm of $r$ is same as $Dr$. So $||y-Dx||_0=||D(D^{-1}y-x)||_0=||D^{-1}y-x||_0$. $D^{-1}y$ is a known vector, and now you follow the previous method for the identity matrix case.

No Need to Read after this, it is still in development :). I just scribbled my thoughts here.

Consider the case $A$ is such that $A^TA$ is diagonal. Then make the observation that $A$ should be of the form $A=UD$ where $U$ is some orthognal matrix and $D$ is some diagonal matrix. Define $v=U^Ty-Dx$ Observe that $||y-UDx||_0=||U(U^Ty-Dx)||_0=||Uv||_0$. Now when is this minimized (if one forgets about the constraints). One possibility is $Uv=0$, so you get the minimum as 0. This is not possible because $U$ is orthogonal. What is the next best answer, can ||Uv|| be such that only one of the entries of is non-zero?. Now one intepretation of $U$ is that it is an orthogonal matrix as well as a rotation matrix and also it preserves the norm.

share|cite|improve this answer
    
Nice thoughts, your intuitions for the $p=0$ case are spot on, I am still thinking about the latter part though :) – Ahmed Dec 19 '12 at 9:42
    
If it helps, i can be more specific.. $U$ is a rotation matrix. – Ahmed Dec 19 '12 at 10:09
    
I already saw that. But the whole thing doesn't answer what you actually want, the behavior for small $p$. But I am sure, some literature from Compressive Sensing Community should be doing something about it. – dineshdileep Dec 19 '12 at 11:04
    
From the top of my head: $||Ax||_2^2=N $ for the discrete points $|[x]_i|=1/\sqrt(n)~\forall~i\in\{1,2,...,n\}$. I don't know if $||Ax||_2^2=N $ holds for other combinations of $x$ or not. What if we were interested in these specific points, i.e., all $x$ for which ||Ax||_2^2=N? Let's say Ax=k, then the minimization is reducing the cost $||y-k||$ where $||k||_2^2=N$. which in essence is the similar to the case in your answer where $A=I$. – Ahmed Dec 19 '12 at 11:21
    
I didn't get your comment. But I think it has been observed in literature that as $p$ tends to zero, more and more sparser solutions are promoted. – dineshdileep Dec 19 '12 at 13:58

the paper of rick chartrand(2012), "nonconvex splitting for regularized low-rank + sparse decomposition", seems for me somehow related to your problem. Some thoughts/guesses: Even if your problem is non-convex, it might be solvable iteratively by a sequence of convex problems via splitting methods (as described e.g. in 'Proximal Splitting Methods in Signal Processing' by combettes). Also you might prefer to transform the hard constraint '||x|| = 1' into a penalty term '+ lambda * (||x|| - 1)^2'.

share|cite|improve this answer
    
Thank you Richard, i will look into it! – Ahmed Dec 24 '12 at 14:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.