Standard sparse decomposition (with applications in many different areas including compressive sampling) amounts to finding the minimum ℓ⁰-norm solution of an underdetermined system of linear equations. In this decomposition, all atoms are treated `uniformly' for being included or not in the decomposition. However, one may wish to weigh more or less certain atoms, or, assign higher costs to some other atoms to be included in the decomposition. This can happen for example when there is prior information available on each atom. This motivates generalizing the notion of minimal ℓ⁰-norm solution to that of minimal weighted ℓ⁰-norm solution. On the other hand, relaxing weighted ℓ⁰-norm via the weighted ℓ¹-norm is challenging. This paper deals with minimal weighted ℓ⁰-norm solutions of underdetermined linear systems, provides conditions for their uniqueness, and develops an algorithm for their estimation.