In-crowd algorithm - Revision history

GreenC bot: Move 1 url. Wayback Medic 2.5 per WP:URLREQ#ieee.org

2024-07-31T03:56:00Z

Move 1 url. Wayback Medic 2.5 per WP:URLREQ#ieee.org

← Previous revision		Revision as of 03:56, 31 July 2024
Line 1:		Line 1:
	The '''in-crowd algorithm''' is a numerical method for solving [[basis pursuit denoising]] quickly; faster than any other algorithm for large, sparse problems.<ref name="in_crowd">See ''The In-Crowd Algorithm for Fast Basis Pursuit Denoising'', IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, [~~http~~://ieeexplore.ieee.org/~~xpl~~/~~freeabs_all.jsp~~?arnumber=5940245], demo [[MATLAB]] code available [http://molnargroup.ece.cornell.edu/files/InCrowdBeta1.zip]</ref> This algorithm is an [[active set method]], which minimizes iteratively sub-problems of the global basis pursuit denoising:		The '''in-crowd algorithm''' is a numerical method for solving [[basis pursuit denoising]] quickly; faster than any other algorithm for large, sparse problems.<ref name="in_crowd">See ''The In-Crowd Algorithm for Fast Basis Pursuit Denoising'', IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, [https://ieeexplore.ieee.org/document/5940245/;jsessionid=8C87F84B1E82E90A4740FE46AF0BCCD2?arnumber=5940245], demo [[MATLAB]] code available [http://molnargroup.ece.cornell.edu/files/InCrowdBeta1.zip]</ref> This algorithm is an [[active set method]], which minimizes iteratively sub-problems of the global basis pursuit denoising:

	<math>\min_x \frac{1}{2}\\|y-Ax\\|^2_2+\lambda\\|x\\|_1.</math>		<math>\min_x \frac{1}{2}\\|y-Ax\\|^2_2+\lambda\\|x\\|_1.</math>

Amaurea: /* Algorithm */ Clarify unexplained I^c

2022-12-03T12:52:04Z

Algorithm: Clarify unexplained I^c

← Previous revision		Revision as of 12:52, 3 December 2022
Line 12:		Line 12:

	# Declare <math>x</math> to be 0, so the unexplained residual <math> r = y</math>		# Declare <math>x</math> to be 0, so the unexplained residual <math> r = y</math>
	# Declare the active set <math>I</math> to be the empty set		# Declare the active set <math>I</math> to be the empty set, and <math>I^c</math> to be its complement (the inactive set)
	# Calculate the usefulness <math>u_j = \| \langle r A_j \rangle \| </math> for each component in <math>I^c</math>		# Calculate the usefulness <math>u_j = \| \langle r A_j \rangle \| </math> for each component in <math>I^c</math>
	# If on <math>I^c</math>, no <math>u_j > \lambda</math>, terminate		# If on <math>I^c</math>, no <math>u_j > \lambda</math>, terminate

Frap: /* In-crowd Algorithm */

2019-11-27T12:52:23Z

In-crowd Algorithm

← Previous revision		Revision as of 12:52, 27 November 2019
Line 7:		Line 7:
	Other active-set methods for the basis pursuit denoising includes BLITZ,<ref>Johnson T, Guestrin C. Blitz: ''A principled meta-algorithm for scaling sparse optimization''. In proceedings of the International Conference on Machine Learning (ICML) 2015 (pp. 1171-1179).([http://proceedings.mlr.press/v37/johnson15.pdf])</ref> where the selection of the active set is performed using the [[duality gap]] of the problem, and The Feature Sign Search,<ref>Lee H, Battle A, Raina R, Ng AY. ''Efficient sparse coding algorithms''. In Advances in neural information processing systems 2007 (pp. 801-808). [https://papers.nips.cc/paper/2979-efficient-sparse-coding-algorithms.pdf]</ref> where the features are included based on the estimate of their sign.		Other active-set methods for the basis pursuit denoising includes BLITZ,<ref>Johnson T, Guestrin C. Blitz: ''A principled meta-algorithm for scaling sparse optimization''. In proceedings of the International Conference on Machine Learning (ICML) 2015 (pp. 1171-1179).([http://proceedings.mlr.press/v37/johnson15.pdf])</ref> where the selection of the active set is performed using the [[duality gap]] of the problem, and The Feature Sign Search,<ref>Lee H, Battle A, Raina R, Ng AY. ''Efficient sparse coding algorithms''. In Advances in neural information processing systems 2007 (pp. 801-808). [https://papers.nips.cc/paper/2979-efficient-sparse-coding-algorithms.pdf]</ref> where the features are included based on the estimate of their sign.

	==~~In-crowd~~ Algorithm==		==Algorithm==

	It consists of the following:		It consists of the following:

Harryboyles: clean up; fix heading levels

2019-09-23T07:07:53Z

clean up; fix heading levels

← Previous revision		Revision as of 07:07, 23 September 2019
Line 5:		Line 5:
	where <math>y</math> is the observed signal, <math>x</math> is the sparse signal to be recovered, <math>Ax</math> is the expected signal under <math>x</math>, and <math>\lambda</math> is the regularization parameter trading off signal fidelity and simplicity. The simplicity is here measured using the sparsity of the solution <math>x</math>, measure through its <math>\ell_1</math>-norm. The active set strategies are very efficient in this context as only few coefficient are expected to be non-zero. Thus, if they can be identified, solving the problem restricted to these coefficients yield the solution. Here, the features are greedily selected based on the absolute value of their gradient at the current estimate.		where <math>y</math> is the observed signal, <math>x</math> is the sparse signal to be recovered, <math>Ax</math> is the expected signal under <math>x</math>, and <math>\lambda</math> is the regularization parameter trading off signal fidelity and simplicity. The simplicity is here measured using the sparsity of the solution <math>x</math>, measure through its <math>\ell_1</math>-norm. The active set strategies are very efficient in this context as only few coefficient are expected to be non-zero. Thus, if they can be identified, solving the problem restricted to these coefficients yield the solution. Here, the features are greedily selected based on the absolute value of their gradient at the current estimate.

	Other active-set methods for the basis pursuit denoising includes BLITZ<ref> Johnson T, Guestrin C. Blitz: ''A principled meta-algorithm for scaling sparse optimization''. In proceedings of the International Conference on Machine Learning (ICML) 2015 (pp. 1171-1179).([http://proceedings.mlr.press/v37/johnson15.pdf])</ref>, where the selection of the active set is performed using the [[duality gap]] of the problem, and The Feature Sign Search<ref>Lee H, Battle A, Raina R, Ng AY. ''Efficient sparse coding algorithms''. In Advances in neural information processing systems 2007 (pp. 801-808). [https://papers.nips.cc/paper/2979-efficient-sparse-coding-algorithms.pdf]</ref>, where the features are included based on the estimate of their sign.		Other active-set methods for the basis pursuit denoising includes BLITZ,<ref>Johnson T, Guestrin C. Blitz: ''A principled meta-algorithm for scaling sparse optimization''. In proceedings of the International Conference on Machine Learning (ICML) 2015 (pp. 1171-1179).([http://proceedings.mlr.press/v37/johnson15.pdf])</ref> where the selection of the active set is performed using the [[duality gap]] of the problem, and The Feature Sign Search,<ref>Lee H, Battle A, Raina R, Ng AY. ''Efficient sparse coding algorithms''. In Advances in neural information processing systems 2007 (pp. 801-808). [https://papers.nips.cc/paper/2979-efficient-sparse-coding-algorithms.pdf]</ref> where the features are included based on the estimate of their sign.

	=In-crowd Algorithm=		==In-crowd Algorithm==

	It consists of the following:		It consists of the following:
Line 21:		Line 21:

	Since every time the in-crowd algorithm performs a global search it adds up to <math>L</math> components to the active set, it can be a factor of <math>L</math> faster than the best alternative algorithms when this search is computationally expensive. A theorem<ref name="in_crowd"/> guarantees that the global optimum is reached in spite of the many-at-a-time nature of the in-crowd algorithm.		Since every time the in-crowd algorithm performs a global search it adds up to <math>L</math> components to the active set, it can be a factor of <math>L</math> faster than the best alternative algorithms when this search is computationally expensive. A theorem<ref name="in_crowd"/> guarantees that the global optimum is reached in spite of the many-at-a-time nature of the in-crowd algorithm.


	==Notes==		==Notes==

TomMoral: Add link to active set methods and some other related techniques (BLITZ, FSS).

2019-03-23T08:39:21Z

Add link to active set methods and some other related techniques (BLITZ, FSS).

← Previous revision		Revision as of 08:39, 23 March 2019
Line 1:		Line 1:
	The '''in-crowd algorithm''' is a numerical method for solving [[basis pursuit denoising]] quickly; faster than any other algorithm for large, sparse problems.<ref>See ''The In-Crowd Algorithm for Fast Basis Pursuit Denoising'', IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5940245], demo [[MATLAB]] code available [http://molnargroup.ece.cornell.edu/files/InCrowdBeta1.zip]</ref> ~~Basis~~ ~~pursuit~~ ~~denoising~~ is the ~~following~~ ~~optimization~~ ~~problem~~:		The '''in-crowd algorithm''' is a numerical method for solving [[basis pursuit denoising]] quickly; faster than any other algorithm for large, sparse problems.<ref name="in_crowd">See ''The In-Crowd Algorithm for Fast Basis Pursuit Denoising'', IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5940245], demo [[MATLAB]] code available [http://molnargroup.ece.cornell.edu/files/InCrowdBeta1.zip]</ref> This algorithm is an [[active set method]], which minimizes iteratively sub-problems of the global basis pursuit denoising:

	<math>\min_x \frac{1}{2}\\|y-Ax\\|^2_2+\lambda\\|x\\|_1.</math>		<math>\min_x \frac{1}{2}\\|y-Ax\\|^2_2+\lambda\\|x\\|_1.</math>

	where <math>y</math> is the observed signal, <math>x</math> is the sparse signal to be recovered, <math>Ax</math> is the expected signal under <math>x</math>, and <math>\lambda</math> is the regularization parameter trading off signal fidelity and simplicity.		where <math>y</math> is the observed signal, <math>x</math> is the sparse signal to be recovered, <math>Ax</math> is the expected signal under <math>x</math>, and <math>\lambda</math> is the regularization parameter trading off signal fidelity and simplicity. The simplicity is here measured using the sparsity of the solution <math>x</math>, measure through its <math>\ell_1</math>-norm. The active set strategies are very efficient in this context as only few coefficient are expected to be non-zero. Thus, if they can be identified, solving the problem restricted to these coefficients yield the solution. Here, the features are greedily selected based on the absolute value of their gradient at the current estimate.

			Other active-set methods for the basis pursuit denoising includes BLITZ<ref> Johnson T, Guestrin C. Blitz: ''A principled meta-algorithm for scaling sparse optimization''. In proceedings of the International Conference on Machine Learning (ICML) 2015 (pp. 1171-1179).([http://proceedings.mlr.press/v37/johnson15.pdf])</ref>, where the selection of the active set is performed using the [[duality gap]] of the problem, and The Feature Sign Search<ref>Lee H, Battle A, Raina R, Ng AY. ''Efficient sparse coding algorithms''. In Advances in neural information processing systems 2007 (pp. 801-808). [https://papers.nips.cc/paper/2979-efficient-sparse-coding-algorithms.pdf]</ref>, where the features are included based on the estimate of their sign.

			=In-crowd Algorithm=

	It consists of the following:		It consists of the following:
Line 16:		Line 20:
	# Go to step 3.		# Go to step 3.

	Since every time the in-crowd algorithm performs a global search it adds up to <math>L</math> components to the active set, it can be a factor of <math>L</math> faster than the best alternative algorithms when this search is computationally expensive. A theorem<ref~~>See~~ ~~''The In-Crowd Algorithm for Fast Basis Pursuit Denoising'', IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber~~=~~5940245]<~~/~~ref~~> guarantees that the global optimum is reached in spite of the many-at-a-time nature of the in-crowd algorithm.		Since every time the in-crowd algorithm performs a global search it adds up to <math>L</math> components to the active set, it can be a factor of <math>L</math> faster than the best alternative algorithms when this search is computationally expensive. A theorem<ref name="in_crowd"/> guarantees that the global optimum is reached in spite of the many-at-a-time nature of the in-crowd algorithm.


	==Notes==		==Notes==

Marcocapelle: removed Category:Mathematical optimization; added Category:Optimization algorithms and methods using HotCat

2018-02-08T21:28:22Z

removed Category:Mathematical optimization; added Category:Optimization algorithms and methods using HotCat

← Previous revision		Revision as of 21:28, 8 February 2018
Line 21:		Line 21:
	{{reflist}}		{{reflist}}

	[[Category:~~Mathematical~~ ~~optimization~~]]		[[Category:Optimization algorithms and methods]]

Austrartsua at 23:29, 14 October 2014

2014-10-14T23:29:23Z

← Previous revision		Revision as of 23:29, 14 October 2014
Line 11:		Line 11:
	# Calculate the usefulness <math>u_j = \| \langle r A_j \rangle \| </math> for each component in <math>I^c</math>		# Calculate the usefulness <math>u_j = \| \langle r A_j \rangle \| </math> for each component in <math>I^c</math>
	# If on <math>I^c</math>, no <math>u_j > \lambda</math>, terminate		# If on <math>I^c</math>, no <math>u_j > \lambda</math>, terminate
	# Otherwise, add <math>L \approx 25</math> components to <math>I</math>		# Otherwise, add <math>L \approx 25</math> components to <math>I</math> based on their usefulness
	# Solve basis pursuit denoising exactly on <math>I</math>, and throw out any component of <math>I</math> whose value attains exactly 0. This problem is dense, so quadratic programming techniques work very well for this sub problem.		# Solve basis pursuit denoising exactly on <math>I</math>, and throw out any component of <math>I</math> whose value attains exactly 0. This problem is dense, so quadratic programming techniques work very well for this sub problem.
	# Update <math> r = y - Ax</math> - n.b. can be computed in the subproblem as all elements outside of <math>I</math> are 0		# Update <math> r = y - Ax</math> - n.b. can be computed in the subproblem as all elements outside of <math>I</math> are 0

BG19bot: WP:CHECKWIKI error fix for #61. Punctuation goes before References. Do general fixes if a problem exists. - using AWB (8853)

2013-01-10T23:46:21Z

WP:CHECKWIKI error fix for #61. Punctuation goes before References. Do general fixes if a problem exists. - using AWB (8853)

← Previous revision		Revision as of 23:46, 10 January 2013
Line 1:		Line 1:
	The in-crowd algorithm is a numerical method for solving [[basis pursuit denoising]] quickly; faster than any other algorithm for large, sparse problems<ref>See ''The In-Crowd Algorithm for Fast Basis Pursuit Denoising'', IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5940245], demo [[MATLAB]] code available [http://molnargroup.ece.cornell.edu/files/InCrowdBeta1.zip]</ref>. Basis pursuit denoising is the following optimization problem:		The '''in-crowd algorithm''' is a numerical method for solving [[basis pursuit denoising]] quickly; faster than any other algorithm for large, sparse problems.<ref>See ''The In-Crowd Algorithm for Fast Basis Pursuit Denoising'', IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5940245], demo [[MATLAB]] code available [http://molnargroup.ece.cornell.edu/files/InCrowdBeta1.zip]</ref> Basis pursuit denoising is the following optimization problem:

	<math>\min_x \frac{1}{2}\\|y-Ax\\|^2_2+\lambda\\|x\\|_1.</math>		<math>\min_x \frac{1}{2}\\|y-Ax\\|^2_2+\lambda\\|x\\|_1.</math>
Line 19:		Line 19:

	==Notes==		==Notes==
	{{reflist}}		{{reflist}}

	[[Category:Mathematical optimization]]		[[Category:Mathematical optimization]]

Patrick Gill: ←Created page with 'The in-crowd algorithm is a numerical method for solving basis pursuit denoising quickly; faster than any other algorithm for large, sparse problemsSee ...'

2011-11-07T19:47:50Z

←Created page with 'The in-crowd algorithm is a numerical method for solving basis pursuit denoising quickly; faster than any other algorithm for large, sparse problems<ref>See ...'

New page

The in-crowd algorithm is a numerical method for solving [[basis pursuit denoising]] quickly; faster than any other algorithm for large, sparse problems<ref>See ''The In-Crowd Algorithm for Fast Basis Pursuit Denoising'', IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5940245], demo [[MATLAB]] code available [http://molnargroup.ece.cornell.edu/files/InCrowdBeta1.zip]</ref>. Basis pursuit denoising is the following optimization problem:

<math>\min_x \frac{1}{2}\|y-Ax\|^2_2+\lambda\|x\|_1.</math>

where <math>y</math> is the observed signal, <math>x</math> is the sparse signal to be recovered, <math>Ax</math> is the expected signal under <math>x</math>, and <math>\lambda</math> is the regularization parameter trading off signal fidelity and simplicity.

It consists of the following:

# Declare <math>x</math> to be 0, so the unexplained residual <math> r = y</math>
# Declare the active set <math>I</math> to be the empty set
# Calculate the usefulness <math>u_j = | \langle r A_j \rangle | </math> for each component in <math>I^c</math>
# If on <math>I^c</math>, no <math>u_j > \lambda</math>, terminate
# Otherwise, add <math>L \approx 25</math> components to <math>I</math>
# Solve basis pursuit denoising exactly on <math>I</math>, and throw out any component of <math>I</math> whose value attains exactly 0. This problem is dense, so quadratic programming techniques work very well for this sub problem.
# Update <math> r = y - Ax</math> - n.b. can be computed in the subproblem as all elements outside of <math>I</math> are 0
# Go to step 3.

Since every time the in-crowd algorithm performs a global search it adds up to <math>L</math> components to the active set, it can be a factor of <math>L</math> faster than the best alternative algorithms when this search is computationally expensive. A theorem<ref>See ''The In-Crowd Algorithm for Fast Basis Pursuit Denoising'', IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5940245]</ref> guarantees that the global optimum is reached in spite of the many-at-a-time nature of the in-crowd algorithm.

==Notes==
{{reflist}}
[[Category:Mathematical optimization]]

{{Mathapplied-stub}}