The Simplest Solution to an Underdetermined System of Linear Equations
<|reference_start|>The Simplest Solution to an Underdetermined System of Linear Equations: Consider a d*n matrix A, with d<n. The problem of solving for x in y=Ax is underdetermined, and has infinitely many solutions (if there are any). Given y, the minimum Kolmogorov complexity solution (MKCS) of the input x is defined to be an input z (out of many) with minimum Kolmogorov-complexity that satisfies y=Az. One expects that if the actual input is simple enough, then MKCS will recover the input exactly. This paper presents a preliminary study of the existence and value of the complexity level up to which such a complexity-based recovery is possible. It is shown that for the set of all d*n binary matrices (with entries 0 or 1 and d<n), MKCS exactly recovers the input for an overwhelming fraction of the matrices provided the Kolmogorov complexity of the input is O(d). A weak converse that is loose by a log n factor is also established for this case. Finally, we investigate the difficulty of finding a matrix that has the property of recovering inputs with complexity of O(d) using MKCS.<|reference_end|>
@article{donoho2007the,
    title={The Simplest Solution to an Underdetermined System of Linear Equations},
    author={David Donoho, Hossein Kakavand, James Mammen},
    journal={arXiv preprint arXiv:cs/0702105},
    year={2007},
    doi={10.1109/ISIT.2006.261816},
    archivePrefix={arXiv},
    eprint={cs/0702105},
    primaryClass={cs.IT math.IT}
}