Many thanks! Can you suggest me any technique/algorithm that I can use to solve my problem. Even a suboptimal solution would be enough.

yes assumption means a requirement. In other words, $\exists$ $s$ rows of $B$ that we don't know their indices and minimize $f(x)$

@D.W. $0_{n,1}$ refers to $n$-dimensional vector where all entries are zeros. The $s$ rows can be any set from all the $n$ rows of $B$ and so we have $n\choose s$ possible submatrices and we are looking to find the set that corresponds to the least $f(x)$.

can you have a look at this question: cs.stackexchange.com/questions/22333/…

Actually the norm doesn't matter because I am looking to measure the error. In other words I am looking to see how $X$ is far from $\hat{X}$