The next lemma reduces the approximate linear search problem for intermediate sparsities to approximate linear search problem on dense PSD matrices. It's proof exploits the fact that the algorithm of Yuster and Zwick [1]} does matrix multiplication of two matrices \(A, A^{\prime }\)  in \(O(\min (n^{\omega }, z^{.7}n^{1.2}+n^2))\)  time where \(z \ge \text{nnz}(A)\)  and \(z > \text{nnz}(A^{\prime })\) . This is faster than the best algorithm for solving linear systems \((A, b)\)  which runs in \(O(\min (n^{\omega }, zn))\)  where \(z = \text{nnz}(A)\)  for certain sparsities. Specifically we will use the following result from Yuster and Zwick [1]}:
