Cédric Josz

Richard Y. Zhang, Cédric Josz, Somayeh Sojoudi

Optimization is at the core of control theory and appears in several areas of this field, such as optimal control, distributed control, system identification, robust control, state estimation, model predictive control and dynamic programming. The recent advances in various topics of modern optimization have also been revamping the area of machine learning. Motivated by the crucial role of optimization theory in the design, analysis, control and operation of real-world systems, this tutorial paper offers a detailed overview of some major advances in this area, namely conic optimization and its emerging applications. First, we discuss the importance of conic optimization in different areas. Then, we explain seminal results on the design of hierarchies of convex relaxations for a wide range of nonconvex problems. Finally, we study different numerical algorithms for large-scale conic optimization problems.

Théodore Fougereux, Cédric Josz, Xiaopeng Li

We propose a tensor-based criterion for benign landscape in phase retrieval and establish boundedness of gradient trajectories. This implies that gradient descent will converge to a global minimum for almost every initial point.

Richard Y. Zhang, Cédric Josz, Somayeh Sojoudi et al.

When the linear measurements of an instance of low-rank matrix recovery satisfy a restricted isometry property (RIP)---i.e. they are approximately norm-preserving---the problem is known to contain no spurious local minima, so exact recovery is guaranteed. In this paper, we show that moderate RIP is not enough to eliminate spurious local minima, so existing results can only hold for near-perfect RIP. In fact, counterexamples are ubiquitous: we prove that every x is the spurious local minimum of a rank-1 instance of matrix recovery that satisfies RIP. One specific counterexample has RIP constant $δ=1/2$, but causes randomly initialized stochastic gradient descent (SGD) to fail 12% of the time. SGD is frequently able to avoid and escape spurious local minima, but this empirical result shows that it can occasionally be defeated by their existence. Hence, while exact recovery guarantees will likely require a proof of no spurious local minima, arguments based solely on norm preservation will only be applicable to a narrow set of nearly-isotropic instances.

Cédric Josz

We consider the problem of solving a linear system of equations which involves complex variables and their conjugates. We characterize when it reduces to a complex linear system, that is, a system involving only complex variables (and not their conjugates). In that case, we show how to construct the complex linear system. Interestingly, this provides a new insight on the relationship between real and complex linear systems. In particular, any real symmetric linear system of equations can be solved via a complex linear system of equations. Numerical illustrations are provided. The mathematics in this manuscript constitute an exciting interplay between Schur's complement, Cholesky's factorization, and Cauchy's interlace theorem.