  In this paper, we consider the problem of recovering random graph signals
from nonlinear measurements. We formulate the maximum a-posteriori probability
(MAP) estimator, which results in a nonconvex optimization problem.
Conventional iterative methods for minimizing nonconvex problems are sensitive
to the initialization, have high computational complexity, and do not utilize
the underlying graph structure behind the data. In this paper we propose two
new estimators that are both based on the Gauss-Newton method: 1) the
elementwise graph-frequency-domain MAP (eGFD-MAP) estimator; and 2) the graph
signal processing MAP (GSP-MAP) estimator. At each iteration, these estimators
are updated by the outputs of two graph filters, with the previous state
estimator and the residual as the input graph signals. The eGFD-MAP estimator
is an ad-hoc method that minimizes the MAP objective function in the graph
frequency domain and neglects mixed-derivatives of different graph frequencies
in the Jacobian matrix as well as off-diagonal elements in the covariance
matrices. Consequently, it updates the elements of the graph signal
independently, which reduces the computational complexity compared to the
conventional MAP estimator. The GSP-MAP estimator is based on optimizing the
graph filters at each iteration of the Gauss-Newton algorithm. We state
conditions under which the eGFD-MAP and GSP- MAP estimators coincide with the
MAP estimator, in the case of an observation model with orthogonal graph
frequencies. We evaluate the performance of the estimators for nonlinear graph
signal recovery tasks with synthetic data and with the real-world problem of
state estimation in power systems. These simulations show the advantages of the
proposed estimators in terms of computational complexity, mean-squared-error,
and robustness to the initialization of the iterative algorithms.
