Mixing
Sparse recovery with L1 shrinkage iteration for higher denominational image classification
up vote
0
down vote
favorite
For 2 months I have been studying sparse recovery and its applications for image classification and I have found that it's a broad area in mathematics which gives rise to a wide variety of regularization techniques. However, I am struggling to understand and implement the sparse recovery of the sparse vector by $L_1$ shrinkage iteration based on prior knowledge of labels.
Actually, I have a dictionary size $200 times 58000$ (fat matrix) which constructed by a prior knowledge of classes (which needs to be redundant), and I have the knowledge of labels and I try to find the $L^1$ optimal solution using soft-shrinkage iteration which is as follows:
We have the linear combination.
$$y = Dx$$
and we use the least squares method to minimize $x$
$$|y - Dx|^2 + lambda|x|_1tomin_x$$
My question is, how to compute the $x$ first and then create an iterative method to update its quantity?
Or should I initialize $x$ to e.g $0$ and then wrap it with an iterative method to be updated? if so, how to formulate that particular iterative method?
Appreciate your help and response.
Edited
Is the following equation the derivation of least squire with $L_1$?
How can I end up to the following equation?
Note: Of course the superscripts denote the number of iterations.
$$x^{n+1} = Slambda /2(x^n + D^T(y - D x^n)) $$
least-squares regularization sparse-matrices sparsity
asked Nov 15 at 23:56
morteza
35
add a comment |
up vote
0
down vote
favorite
For 2 months I have been studying sparse recovery and its applications for image classification and I have found that it's a broad area in mathematics which gives rise to a wide variety of regularization techniques. However, I am struggling to understand and implement the sparse recovery of the sparse vector by $L_1$ shrinkage iteration based on prior knowledge of labels.
Actually, I have a dictionary size $200 times 58000$ (fat matrix) which constructed by a prior knowledge of classes (which needs to be redundant), and I have the knowledge of labels and I try to find the $L^1$ optimal solution using soft-shrinkage iteration which is as follows:
We have the linear combination.
$$y = Dx$$
and we use the least squares method to minimize $x$
$$|y - Dx|^2 + lambda|x|_1tomin_x$$
My question is, how to compute the $x$ first and then create an iterative method to update its quantity?
Or should I initialize $x$ to e.g $0$ and then wrap it with an iterative method to be updated? if so, how to formulate that particular iterative method?
Appreciate your help and response.
Edited
Is the following equation the derivation of least squire with $L_1$?
How can I end up to the following equation?
Note: Of course the superscripts denote the number of iterations.
$$x^{n+1} = Slambda /2(x^n + D^T(y - D x^n)) $$
least-squares regularization sparse-matrices sparsity
asked Nov 15 at 23:56
morteza
35
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
For 2 months I have been studying sparse recovery and its applications for image classification and I have found that it's a broad area in mathematics which gives rise to a wide variety of regularization techniques. However, I am struggling to understand and implement the sparse recovery of the sparse vector by $L_1$ shrinkage iteration based on prior knowledge of labels.
Actually, I have a dictionary size $200 times 58000$ (fat matrix) which constructed by a prior knowledge of classes (which needs to be redundant), and I have the knowledge of labels and I try to find the $L^1$ optimal solution using soft-shrinkage iteration which is as follows:
We have the linear combination.
$$y = Dx$$
and we use the least squares method to minimize $x$
$$|y - Dx|^2 + lambda|x|_1tomin_x$$
My question is, how to compute the $x$ first and then create an iterative method to update its quantity?
Or should I initialize $x$ to e.g $0$ and then wrap it with an iterative method to be updated? if so, how to formulate that particular iterative method?
Appreciate your help and response.
Edited
Is the following equation the derivation of least squire with $L_1$?
How can I end up to the following equation?
Note: Of course the superscripts denote the number of iterations.
$$x^{n+1} = Slambda /2(x^n + D^T(y - D x^n)) $$
least-squares regularization sparse-matrices sparsity
asked Nov 15 at 23:56
morteza
35
For 2 months I have been studying sparse recovery and its applications for image classification and I have found that it's a broad area in mathematics which gives rise to a wide variety of regularization techniques. However, I am struggling to understand and implement the sparse recovery of the sparse vector by $L_1$ shrinkage iteration based on prior knowledge of labels.
Actually, I have a dictionary size $200 times 58000$ (fat matrix) which constructed by a prior knowledge of classes (which needs to be redundant), and I have the knowledge of labels and I try to find the $L^1$ optimal solution using soft-shrinkage iteration which is as follows:
We have the linear combination.
$$y = Dx$$
and we use the least squares method to minimize $x$
$$|y - Dx|^2 + lambda|x|_1tomin_x$$
My question is, how to compute the $x$ first and then create an iterative method to update its quantity?
Or should I initialize $x$ to e.g $0$ and then wrap it with an iterative method to be updated? if so, how to formulate that particular iterative method?
Appreciate your help and response.
Edited
Is the following equation the derivation of least squire with $L_1$?
How can I end up to the following equation?
Note: Of course the superscripts denote the number of iterations.
$$x^{n+1} = Slambda /2(x^n + D^T(y - D x^n)) $$
least-squares regularization sparse-matrices sparsity
least-squares regularization sparse-matrices sparsity
asked Nov 15 at 23:56
morteza
35
asked Nov 15 at 23:56
morteza
35
edited 17 hours ago
asked Nov 15 at 23:56
morteza
35
asked Nov 15 at 23:56
morteza
35
asked Nov 15 at 23:56
morteza
35
35
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
You may solve the minimisation problem
$$|y-Dx|+lambda|x|_1tomin_x$$
using the so-called Fast Iterative Shrinkage Thresholding Algorithm (FISTA).
It's an iterative method which essentially consists of setting of setting the step size $L$ as the largest eigenvalue of $D^ast D$, the initial values as $z_1=x_0$, $t_1=1$ and iterating
$$z_k=operatorname{prox}_{Lfrac{1}{lambda}|cdot|_1}(y-D^ast(y-Dx_k)),$$
$$t_{k+1}=frac{1+sqrt{1+4t^2_k}}{2},$$
$$x_{k+1}=z_k+left(frac{t_k-1}{t_{k-1}}right)(z_k-z_{k-1}).$$
Note that the nice property of the $|cdot|_1$ regularisation term is that it has a closed form proximal mapping operator:
$$operatorname{prox}_{alpha|cdot|_1}(x)=operatorname{sign}(x_i)max{|x_i|-alpha,0},$$
which is just the soft thresholding operator.
You can read more about FISTA here: FISTA
answered 2 days ago
Kemal Raik
304
Dear Kemal, I do appreciate you for the answer. I have found it helpful. BTW, I have added an Edited part which tells the point which I want.
– morteza
yesterday
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
You may solve the minimisation problem
$$|y-Dx|+lambda|x|_1tomin_x$$
using the so-called Fast Iterative Shrinkage Thresholding Algorithm (FISTA).
It's an iterative method which essentially consists of setting of setting the step size $L$ as the largest eigenvalue of $D^ast D$, the initial values as $z_1=x_0$, $t_1=1$ and iterating
$$z_k=operatorname{prox}_{Lfrac{1}{lambda}|cdot|_1}(y-D^ast(y-Dx_k)),$$
$$t_{k+1}=frac{1+sqrt{1+4t^2_k}}{2},$$
$$x_{k+1}=z_k+left(frac{t_k-1}{t_{k-1}}right)(z_k-z_{k-1}).$$
Note that the nice property of the $|cdot|_1$ regularisation term is that it has a closed form proximal mapping operator:
$$operatorname{prox}_{alpha|cdot|_1}(x)=operatorname{sign}(x_i)max{|x_i|-alpha,0},$$
which is just the soft thresholding operator.
You can read more about FISTA here: FISTA
answered 2 days ago
Kemal Raik
304
Dear Kemal, I do appreciate you for the answer. I have found it helpful. BTW, I have added an Edited part which tells the point which I want.
– morteza
yesterday
add a comment |
up vote
0
down vote
accepted
You may solve the minimisation problem
$$|y-Dx|+lambda|x|_1tomin_x$$
using the so-called Fast Iterative Shrinkage Thresholding Algorithm (FISTA).
It's an iterative method which essentially consists of setting of setting the step size $L$ as the largest eigenvalue of $D^ast D$, the initial values as $z_1=x_0$, $t_1=1$ and iterating
$$z_k=operatorname{prox}_{Lfrac{1}{lambda}|cdot|_1}(y-D^ast(y-Dx_k)),$$
$$t_{k+1}=frac{1+sqrt{1+4t^2_k}}{2},$$
$$x_{k+1}=z_k+left(frac{t_k-1}{t_{k-1}}right)(z_k-z_{k-1}).$$
Note that the nice property of the $|cdot|_1$ regularisation term is that it has a closed form proximal mapping operator:
$$operatorname{prox}_{alpha|cdot|_1}(x)=operatorname{sign}(x_i)max{|x_i|-alpha,0},$$
which is just the soft thresholding operator.
You can read more about FISTA here: FISTA
answered 2 days ago
Kemal Raik
304
Dear Kemal, I do appreciate you for the answer. I have found it helpful. BTW, I have added an Edited part which tells the point which I want.
– morteza
yesterday
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
You may solve the minimisation problem
$$|y-Dx|+lambda|x|_1tomin_x$$
using the so-called Fast Iterative Shrinkage Thresholding Algorithm (FISTA).
It's an iterative method which essentially consists of setting of setting the step size $L$ as the largest eigenvalue of $D^ast D$, the initial values as $z_1=x_0$, $t_1=1$ and iterating
$$z_k=operatorname{prox}_{Lfrac{1}{lambda}|cdot|_1}(y-D^ast(y-Dx_k)),$$
$$t_{k+1}=frac{1+sqrt{1+4t^2_k}}{2},$$
$$x_{k+1}=z_k+left(frac{t_k-1}{t_{k-1}}right)(z_k-z_{k-1}).$$
Note that the nice property of the $|cdot|_1$ regularisation term is that it has a closed form proximal mapping operator:
$$operatorname{prox}_{alpha|cdot|_1}(x)=operatorname{sign}(x_i)max{|x_i|-alpha,0},$$
which is just the soft thresholding operator.
You can read more about FISTA here: FISTA
answered 2 days ago
Kemal Raik
304
You may solve the minimisation problem
$$|y-Dx|+lambda|x|_1tomin_x$$
using the so-called Fast Iterative Shrinkage Thresholding Algorithm (FISTA).
It's an iterative method which essentially consists of setting of setting the step size $L$ as the largest eigenvalue of $D^ast D$, the initial values as $z_1=x_0$, $t_1=1$ and iterating
$$z_k=operatorname{prox}_{Lfrac{1}{lambda}|cdot|_1}(y-D^ast(y-Dx_k)),$$
$$t_{k+1}=frac{1+sqrt{1+4t^2_k}}{2},$$
$$x_{k+1}=z_k+left(frac{t_k-1}{t_{k-1}}right)(z_k-z_{k-1}).$$
Note that the nice property of the $|cdot|_1$ regularisation term is that it has a closed form proximal mapping operator:
$$operatorname{prox}_{alpha|cdot|_1}(x)=operatorname{sign}(x_i)max{|x_i|-alpha,0},$$
which is just the soft thresholding operator.
You can read more about FISTA here: FISTA
answered 2 days ago
Kemal Raik
304
answered 2 days ago
Kemal Raik
304
answered 2 days ago
Kemal Raik
304
answered 2 days ago
Kemal Raik
304
304
Dear Kemal, I do appreciate you for the answer. I have found it helpful. BTW, I have added an Edited part which tells the point which I want.
– morteza
yesterday
add a comment |
Dear Kemal, I do appreciate you for the answer. I have found it helpful. BTW, I have added an Edited part which tells the point which I want.
– morteza
yesterday
Dear Kemal, I do appreciate you for the answer. I have found it helpful. BTW, I have added an Edited part which tells the point which I want.
– morteza
yesterday
Dear Kemal, I do appreciate you for the answer. I have found it helpful. BTW, I have added an Edited part which tells the point which I want.
– morteza
yesterday
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3000515%2fsparse-recovery-with-l1-shrinkage-iteration-for-higher-denominational-image-clas%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
