Finding the minimum number of coordinates to change to get a vector inside a subspace Let $\mathbb F$ be a field (ex. a finite field, or the reals), $A$ a $m\times n$ matrix over $\mathbb F$, and $x\in \mathbb F^n$ a vector. I'm interested in finding the smallest number of coordinates I need to change in $x$ to order to have $Ax=\mathbb 0$. 

What would be an algorithm to find this, or alternatively, an intractability result (ex. NP-completeness)?

Note: I am thinking of this in the context of matrix rigidity.
This problem is NP-hard in general.

This is equivalent to finding the sparsest vector $y\in \mathbb F^n$ such that 
$$Ay = -Ax$$

As finding a sparsest solution vector for an underdetermined system of linear equations is NP-hard, so is your problem.