  We consider the CDMA (code-division multiple-access) multi-user detection
problem for binary signals and additive white gaussian noise. We propose a
spreading sequences scheme based on random sparse signatures, and a detection
algorithm based on belief propagation (BP) with linear time complexity. In the
new scheme, each user conveys its power onto a finite number of chips l, in the
large system limit.
  We analyze the performances of BP detection and prove that they coincide with
the ones of optimal (symbol MAP) detection in the l->\infty limit. In the same
limit, we prove that the information capacity of the system converges to
Tanaka's formula for random `dense' signatures, thus providing the first
rigorous justification of this formula. Apart from being computationally
convenient, the new scheme allows for optimization in close analogy with
irregular low density parity check code ensembles.
