Structured matrix recovery and approximation from matrix-vector products