This work considers the problem of locating a single source from noisy range measurements to a set of nodes in a wireless sensor network. We propose two new techniques that we designate as Source Localization with Nuclear Norm (SLNN) and Source Localization with l1-norm (SL-l1), which extend to arbitrary real dimensions our prior work on 2D source localization formulated in the complex plane. Our approach is based on formulating a Maximum-Likelihood (ML) estimation problem, and then using convex relaxation techniques to obtain a semidefinite program (SDP) that can be globally and efficiently solved. SLNN directly approximates the Gaussian ML solution, and the relaxation is shown to be tighter than in other methods in the same class. We present an analysis of the convexity properties of the constraint set for the 2D complex version of SLNN (SLCP) to justify the observed tightness of the relaxation. We propose the SL-l1algorithm to address the Laplacian noise case, which models the presence of outliers in range measurements. We overcome the non-differentiability of the Laplacian likelihood function by rewriting the ML problem as an exact weighted version of the Gaussian case. In terms of accuracy of localization, the proposed algorithms globally outperform state-of-the-art optimization-based methods in different noise scenarios, while exhibiting moderate computational complexity.

This paper describes a new algorithm for recovering the 3D shape and motion of deformable and articulated objects purely from uncalibrated 2D image measurements using an iterative factorization approach. Most solutions to non-rigid and articulated structure from motion require metric constraints to be enforced on the motion matrix to solve for the transformation that upgrades the solution to metric space. While in the case of rigid structure the metric upgrade step is simple since the motion constraints are linear, deformability in the shape introduces non-linearities. In this paper we propose an alternating least-squares approach associated with a globally optimal projection step onto the manifold of metric constraints. An important advantage of this new algorithm is its ability to handle missing data which becomes crucial when dealing with real video sequences with self-occlusions. We show successful results of our algorithms on synthetic and real sequences of both deformable and articulated data.

Finding correspondences between feature points is one of the most relevant problems in the whole set of visual tasks. In this paper we address the problem of matching a feature vector (or a matrix) to a given subspace. Given any vector base of such a subspace, we observe a linear combination of its elements with all entries swapped by an unknown permutation. We prove that such a computationally hard integer problem is uniquely solved in a convex set resulting from relaxing the original problem. Also, if noise is present, based on this result, we provide a robust estimate recurring to a linear programming-based algorithm. We use structure-from-motion and object recognition as motivating examples.

We present an algorithm able to register a known 3D deformable model to a set of 2D matched points extracted from a single image. Unlike previous approaches, the problem is solved simultaneously for both the rigid and non-rigid parameters of the model. The key advantage of our approach is the projection of an initial affine estimation of the motion parameters into the motion manifold corresponding to the exact parametrization of the problem. This projection is formulated as theminimization of the distance between the affine solution and the surface of the manifold. Such optimization results in a quadratically constrained quadratic minimization problem that can be efficiently solved with standard optimization tools. Synthetic and real tests demonstrate the effectiveness of the approach.

From the recovery of structure from motion to the separation of style and content, many problems in computer vision have been successfully approached by using bilinear models. The reason for the success of these models is that a globally optimal decomposition is easily obtained from the singular value decomposition (SVD) of the observation matrix. However, in practice, the observation matrix is often incomplete, the SVD can not be used, and only suboptimal solutions are available. The majority of these solutions are based on iterative local refinements of a given cost function, and lack any guarantee of convergence to the global optimum. In this paper, we propose a globally optimal solution, for particular patterns of missing entries. To achieve this goal, we re-formulate the problem as the minimization of the spectral norm of the matrix of residuals, i.e., we seek the completion of the observation matrix such that the largest singular value of its difference to a low rank matrix is the smallest possible. The class of patterns of missing entries we deal with is known as the Young diagram, which includes, as particular cases, many relevant situations, such as the missing of an entire submatrix. We describe experiments that illustrate how our globally optimal solution has impact in practice.

Widely used SVD-based matrix factorization approaches to the recovery of 3D rigid structure from motion (SFM), require a set of feature points to be visible in a set of images. When there is occlusion, several feature points disappear, the observation matrix misses some entries, there is not equivalent to the SVD, and only suboptimal solutions have been proposed to exploit rigidity. In this paper, we propose a method to complete the trajectories that correspond to a rigid scene, in an optimal way. Our algorithm is not iterative (thus avoiding problems like sensitivity to initialization and local optima); it rather computes in a finite number of steps the globally optimal completion of the observation matrix. We describe experiments that illustrate the gain in accuracy of SFM.