Binary measurements arise naturally in a variety of statistical and engineering applications. They may be inherent to the problem--e.g., in determining the relationship between genetics and the presence or absence of a disease--or they may be a result of extreme quantization. A recent influx of literature has suggested that using prior signal information can greatly improve the ability to reconstruct a signal from binary measurements. This is exemplified by one-bit compressed sensing, which takes the compressed sensing model but assumes that only the sign of each measurement is retained. It has recently been shown that the number of one-bit measurements required for signal estimation mirrors that of unquantized compressed sensing. Indeed, s-sparse signals in Rn can be estimated up to normalization from s logns one-bit measurements. Nevertheless, controlling the precise accuracy of the error estimate remains an open challenge. In this paper, we focus on optimizing the decay of the error as a function of the oversampling factor lambda ms logns, where m is the number of measurements. It is known that the error in reconstructing sparse signals from standard one-bit measurements is bounded below by 1. Without adjusting the measurement procedure, reducing this polynomial error decay rate is impossible.