search

tiepvupsu / FISTA

FISTA implementation in MATLAB (recently updated FISTA with backtracking)
184 stars 61 forks source link

something strange with pL #3

Closed prozaeck closed 6 years ago

prozaeck commented 7 years ago
  1. In the article you refer pL = argmin ( ... , that is the minimization problem. But instead of minimizing you use some sort of projection. Why did you make such a replacement?
  2. In the article you refer pL = (1.5 1.4), for the LASSO problem. Why you didn't use it?
tiepvupsu commented 7 years ago

First of all, FISTA is not my article, I implemented this based on the algorithm proposed there.

  1. For the problems I'm considering, projection is indeed the solution for the optimization problem of pL. If you want to work on different optimization problems other than those in examples, you probably need to implement your own solution for pL.

  2. I don't really understand what is (1.5 1.4), could you please clarify.

prozaeck commented 7 years ago

1.5 1.4 is the formula from the article you REFER.

tiepvupsu commented 7 years ago

Hi,

I'm following the algorithm in the box stated in page 193: FISTA with constant stepsize.

By the way, people don't often mention every piece of equations in the paper, they just need to follow the final algorithm. As long as it works as expected.

prozaeck commented 7 years ago

I'm sure that your FISTA implementation is not optimal for problems with L1 norm. https://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-13.pdf page 7

tiepvupsu commented 7 years ago

Hi friend,

There are more than one ways to solve any problem. That a solution is different from others doesn't mean it's not optimal. I compared my implementation with SPAMS (http://spams-devel.gforge.inria.fr) which is a well-known Sparse Modeling Toolbox, and obtained similar results.

I don't know what you mean by 'not optimal', but if you say you're sure about something, please provide solid evidence.

Bests

tiepvupsu commented 7 years ago

By the way, I just looked at the algorithm in page 7 of the file you sent. There are two things I want to say:

  1. The projection function in my implementation is a combination of Step 6 and Step 7 in your document.

  2. My implementation is "FISTA with constant stepsize" which is located in page 193 of the document I referred. In this case, Lipschitz coefficient is determined. The algorithm you're saying is basically "FISTA with backtracking" (see page 194 in my document) when Lipschitz coefficient is hard to find.

For problems where Lipschitz coefficient could be determined, "FISTA with constant stepsize" should be preferred since we do not need to calculate L in each iteration. For l1 problem, the Lipschitz coefficient is easy to calculate, that is why I used "FISTA with constant stepsize", which is better than "FISTA with backtracking", at least in terms of computational complexity. In other words, "FISTA with constant stepsize" is 'more' optimal than "FISTA with constant stepsize" with l1 norm.

I hope this comment addresses your concern.

Bests,

prozaeck commented 7 years ago

For the problem with L1 norm, the EXACT solution of pL = argmin (...) minimization problem exists. You solve this problem approximately, so your implementation is not optimal.

"The projection function in my implementation is a combination of Step 6 and Step 7" I don't think so. I thik it is coarse approximation 6,7 steps in L1 case.

tiepvupsu commented 7 years ago

How do you say that I solved the problem approximately? That is a soft thresholding function.

tiepvupsu commented 7 years ago

Please understand that the step 7 in your document:

is this one: https://github.com/tiepvupsu/FISTA/blob/master/proj/proj_l1.m

Please read the comment in this file.