LETTERS TO THE EDITORS
Unknowns and Indeterminates
To the Editors:
In “The Best Bits” Brian Hayes uses the familiar situation of solving N linear equations in N unknowns as a lead-in to ideas of the reconstruction of sparse vectors in compressive sensing. He wrote that the solution of a system of N linear equations in N unknowns is unique if the equations are distinct. This is not exactly right. If you think of the linear equations as constraining the variables, you can see that the condition you need is that each equation must provide information not found in the others collectively.
If one equation is a nonzero multiple of another, both give the same information. If one equation can be obtained from the others by addition or subtraction of multiples, it gives no new information. If none of the equations can be derived from the others in this way, the equations are linearly independent and the system has a unique solution. The solution can be ground out by successively eliminating the variables in the set of equations. This is called Guassian elimination.
Compressive sensing looks for sparse vectors as solutions to linear systems with far fewer equations than variables. If the original system violates the sparseness condition, there is no guarantee that the reconstruction will be accurate, but the examples show that the method works well and the mathematical approach is clearly set out. Thank you, Computing Science.
Mr. Hayes responds:
Of course Dr. Renz is correct.
Another statement in the same column also calls for clarification. I wrote: “The zeroth power of 0 is 0, but for any other value of x, x0 is equal to 1.” As several readers have pointed out, the value of 00 is a subject of some controversy. There are plausible arguments for assigning the expression a value of either 0 or 1, and so 00 is often taken to be undefined or indeterminate. What I should have said is that in the context of the calculations performed in compressive sensing, it is convenient to define 00 as 0.
Both of these issues are discussed in greater detail at http://bit-player.org/2009/not-up-to-norm.