Does the method use human crowds?

No. In-crowd refers to a computational active set of coefficients.

Why add several variables together?

Batching can reduce the frequency of expensive searches across the entire dictionary.

Does a small residual prove the algorithm has solved the penalized problem?

No. Optimality also involves the L1 penalty and conditions on active and inactive coordinates.

AI Glossary / Mathematics and optimization / Intermediate

In-crowd algorithm

Definition

The In-crowd algorithm is an active-set method for solving an L1-regularized least-squares problem, commonly called basis pursuit denoising. It repeatedly selects promising variables, solves a smaller optimization problem involving those variables, and checks whether excluded variables could improve the solution. Its distinctive feature is admitting several candidates together, reducing the need for frequent full-dictionary searches. It is unrelated to crowdsourcing or crowd counting.

What it means

In sparse reconstruction, a signal may have many possible explanatory components but only a few useful nonzero coefficients. Solving a smaller problem over likely components can be more practical than treating every coefficient as equally active throughout optimization.
The in-crowd is the current active set of variables. Variables outside it are temporarily fixed to zero, but they are reconsidered through global checks. Membership is not permanent: a selected coefficient can become zero and leave. Finding the right support and solving for its coefficients are connected parts of the process.

How it works

Use the objective F(x)=0.5 times ||y-Ax|| squared plus lambda times ||x||_1, with lambda positive. Starting from zero, compute the residual r=y-Ax and examine correlations |A_j transpose r| for inactive columns. Values above lambda indicate a violation of the zero-coordinate optimality condition.
Admit a batch of promising violating variables, solve the restricted problem with the same L1 penalty, remove zero coefficients, and update the residual. Stop only after appropriate active and inactive optimality checks. The original convergence argument assumes exact restricted solves; practical implementations require numerical tolerances and reliable subproblem solutions.

Three practical examples

A sparse signal-reconstruction experiment can use the method when a large dictionary is expected to yield only a few active coefficients.
An imaging research prototype can compare active-set optimization with other solvers for the same regularized objective.
A solver-development team can study whether batching candidate additions reduces expensive full-matrix operations for its particular problem structure.

Think of it this way

Think of assembling a small working team from a large list of candidates, solving a task with that team, and then checking whether anyone outside could materially help. Several candidates can be invited together, and unneeded members can leave. The analogy is limited because the algorithm's decisions come from convex optimization conditions, not social popularity or human judgment.

Worked example

Consider an original three-variable example chosen for transparent arithmetic rather than large-scale realism. Let A be the 3-by-3 identity matrix, y=(3,0.4,-2), and lambda=1. The objective separates into three independent scalar problems: each coefficient trades squared fit error against its absolute magnitude.
Start with x=(0,0,0), so r=y. The absolute correlations are 3, 0.4, and 2. Variables one and three exceed lambda, while variable two does not. With a batch capacity of two, both violating variables can enter the active set together.
Solve the restricted problem exactly. For the positive first coordinate, minimizing 0.5(3-x1)^2+|x1| gives x1=2. For the negative third coordinate, minimizing 0.5(-2-x3)^2+|x3| gives x3=-1. The inactive second coordinate remains zero. The resulting vector is x=(2,0,-1), with residual r=(1,0.4,-1).
Check the optimality conditions. The inactive coordinate has absolute residual correlation 0.4, which is no greater than lambda. The active coordinates have residual correlations 1 and -1, matching lambda times their coefficient signs. Together these conditions establish optimality for this convex objective; here the identity matrix also makes the minimizer unique.
The zero vector's objective is 0.5 times (9+0.16+4)=6.58. The new vector's fit term is 0.5 times (1+0.16+1)=1.08, and its L1 penalty is |2|+0+|-1|=3. The total is 4.08. The residual is not zero because the objective intentionally balances fit against regularization.
An unregularized solve on the selected coordinates would instead use x=(3,0,-2), whose objective under the original penalized problem is 0.08+5=5.08. This demonstrates why keeping the L1 penalty in the restricted solve matters. The tiny square system illustrates the mechanism; it is not an underdetermined reconstruction benchmark or a speed comparison.

Illustrative case study

Fictional case: a signal-processing group works with a dictionary containing many possible components. Profiling shows that repeatedly searching the full dictionary dominates its current solver's time.
The group tests batched additions with In-crowd, checks final optimality residuals, and compares objective values at matched tolerances. It finds that batch size changes the balance between global screening and restricted solves, so it selects a configuration from representative experiments rather than treating one published setting as universally best.

Common misconceptions and mistakes

Do not claim the algorithm is faster than every alternative on every sparse problem. The original paper reports particular experimental regimes and also discusses settings where alternatives are faster. Matrix structure, sparsity, solver implementation, and accuracy requirements all matter.
Do not mistake an active-set method for permanently choosing variables through a single greedy pass. Excluded variables need further checks, and selected variables can leave. Solving only an unregularized least-squares subproblem changes the algorithm's objective. Also distinguish a global optimum of the mathematical problem from recovery of the true physical signal; a misspecified model can be optimized correctly and still be unsuitable.

Business use

In-crowd is relevant when an organization repeatedly solves sparse regularized least-squares problems and full-variable operations are expensive. It is a specialized numerical method, so its business benefit should be assessed within the complete reconstruction or modeling workflow.
Specify the objective scaling and lambda, normalize columns consistently where required, and compare solvers at comparable accuracy. Track active-set sizes, subproblem work, and global screening costs. Validate the reconstructed outputs separately from optimization convergence. A smaller objective is evidence about the chosen model, not a substitute for task-level validation.

Check your understanding

Why is x=(3,0,-2) worse than x=(2,0,-1) for the stated objective despite fitting more closely?

Answer: Its larger L1 penalty outweighs the reduced squared error. Its total objective is 5.08 rather than 4.08.

Related terms

Active-set method
Convex optimization
Basis pursuit denoising
L1 regularization
Sparse reconstruction
Residual correlation
KKT conditions
Working set
Soft thresholding

Learn next

Repeat the identity-matrix example with lambda=0.5. Determine which coordinates become nonzero and verify both the residual-correlation conditions and the final objective. Explain why changing lambda changes the optimization problem rather than merely making the solver more accurate.

Sources

Primary research: Gill, Wang, and Molnar, The In-Crowd Algorithm for Fast Basis Pursuit Denoising, DOI https://doi.org/10.1109/TSP.2011.2161292 . Accessible original-paper transcription: https://paperzz.com/doc/7322240/the-in-crowd-algorithm-for-fast-basis-pursuit-denoising . The identity-matrix example and optimality calculations are original.

Previous: Imputation variance Next: In-group bias