The convergence and the complexity of a primal-dual column generation and cutting plane algorithm from approximate analytic centers for solving convex feasibility problems defined by a "deep cut" separation oracle is studied. The primal-dual infeasible Newton method is used to generate a primal-dual updating direction. In the case where the cut goes through the analytic center the number of recentering steps is at most three, while it is O(1) for cuts as deep as half way to the deep cut where the deepest cut is a cut that is tangent to the primal-dual variant of Dikin's ellipsoid.