In the first part of this paper, we consider nonlinear extension of frame theory by introducing bi-Lipschitz maps
F between Banach spaces. Our linear model of bi-Lipschitz maps is the analysis operator associated with Hilbert frames,
p-frames, Banach frames, g-frames and fusion frames. In general Banach space setting, stable algorithms to reconstruct a signal
x from its noisy measurement
\(F(x)+\epsilon \) may not exist. In this paper, we establish exponential convergence of two iterative reconstruction algorithms when
F is not too far from some bounded below linear operator with bounded pseudo-inverse, and when
F is a well-localized map between two Banach spaces with dense Hilbert subspaces. The crucial step to prove the latter conclusion is a novel fixed point theorem for a well-localized map on a Banach space. In the second part of this paper, we consider stable reconstruction of sparse signals in a union
\(\mathbf{A}\) of closed linear subspaces of a Hilbert space
\(\mathbf{H}\) from their nonlinear measurements. We introduce an optimization framework called a sparse approximation triple
\((\mathbf{A}, \mathbf{M}, \mathbf{H})\), and show that the minimizer
$$\begin{aligned} x^*=\mathrm{argmin}_{\hat{x}\in {\mathbf M}\ \mathrm{with} \ \Vert F(\hat{x})-F(x^0)\Vert \le \epsilon } \Vert \hat{x}\Vert _{\mathbf M} \end{aligned}$$
provides a suboptimal approximation to the original sparse signal
\(x^0\in \mathbf{A}\) when the measurement map
F has the sparse Riesz property and the almost linear property on
\({\mathbf A}\). The above two new properties are shown to be satisfied when
F is not far away from a linear measurement operator
T having the restricted isometry property.