Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
There is no such thing as "highly non-convex", either you are or you're not... –  Patrick Da Silva Dec 19 '12 at 5:55
    
Ok, the problem is non-convex. Let us not bicker about using the perfect term here. What i actually meant, is that the number of minima (traps) in the cost function increases exponentially with $n$. So any thoughts? –  Ahmed Dec 19 '12 at 6:14
1  
no thoughts, I just don't like weird mathematical sentences :) sorry about the no thoughts part. –  Patrick Da Silva Dec 19 '12 at 6:22
1  
I don't quite follow. What does it mean to minimize $\|y-Ax\|_p$ as $p\rightarrow0$? Do you mean to minimize the quantity for small $p$? –  user1551 Dec 19 '12 at 9:10
    
Good question, and yes... I want to minimize the cost $||y-Ax||_p$ for $x$, but i need to do this for $p$ near $0$. The case for $p=0$ is actually of no interest, as $||z||_0=n~\forall~z\in\mathbb{R}^n$. Perhaps you could rephrase the question to remove the doubt, i will be grateful :) –  Ahmed Dec 19 '12 at 9:19
show 2 more comments

2 Answers 2

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|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
add comment

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|improve this answer
    
Thank you Richard, i will look into it! –  Ahmed Dec 24 '12 at 14:39
add comment

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.