  Network Lasso (NL for short) is a methodology for estimating models by
simultaneously fitting and clustering data samples. It often succeeds in
forming clusters thanks to the geometry of the $\ell_1$-regularizer employed
therein, but there might be limitations because of the convexity of the
regularizer. This paper focuses on the cluster structure of NL and develops a
non-convex extension, which we call Network Trimmed Lasso (NTL for short).
Specifically, we first studies a sufficient condition which guarantees the
recovery of latent cluster structure of NL on the basis of the result of Sun et
al. for Convex Clustering, which is a special case of NL. Second, we extend NL
to NTL to incorporate a cardinality constraint, reformulate the non-convex
constrained optimization problem into an equivalent continuous unconstrained
optimization problem, and develop ADMM algorithms. Numerical illustrations
demonstrate that the non-convex extension provides more clear-cut cluster
structure when NL fails to form clusters without incorporating prior knowledge
on the associated parameters.
