Efficient Optimization for Linear Dynamical Systems with Applications to Clustering and Sparse Coding
Linear Dynamical Systems (LDSs) are fundamental tools for modeling spatiotemporal data in various disciplines. Though rich in modeling, analyzing LDSs is not free of difficulty, mainly because LDSs do not comply with Euclidean geometry and hence conventional learning techniques can not be applied directly. In this paper, we propose an efficient projected gradient descent method to minimize a general form of a loss function and demonstrate how clustering and sparse coding with LDSs can be solved by the proposed method efficiently. To this end, we first derive a novel canonical form for representing the parameters of an LDS, and then show how gradient-descent updates through the projection on the space of LDSs can be achieved dexterously. In contrast to previous studies, our solution avoids any approximation in LDS modeling or during the optimization process. Extensive experiments reveal the superior performance of the proposed method in terms of the convergence and classification accuracy over state-of-the-art techniques.
the system parameters [1], the space of LDSs is non-Euclidean. This in turn makes the direct use of traditional techniques (e.g., conventional sparse solvers) inapplicable. To get around the difficulties induced by the non-Euclidean geometry, previous studies (e.g., [11,12,13,5]) resort to various approximations, either in modeling or during optimization. For instance, the authors in [11] approximated the clustering mean by finding the closest sample under a certain embedding. As we will see in our experiments, involving approximations into the solutions exhibits inevitable limitations to the algorithmic performance.
This paper develops a gradient-based method to solve the clustering and sparse coding tasks efficiently without any approximation involved. To this end, we reformulate the optimization problems for these two different tasks and then unify them into one common problem by making use of the kernel trick. However, there exist several challenges to address this common problem efficiently. The first challenge comes from the aforementioned invariance property on the LDS parameters. To attack this challenge, we introduce a novel canonical form of the system parameters that is insensitive to the equivalent changes. The second challenge comes from the fact that the optimization problem of interest requires solving Discrete Lyapunov Equations (DLEs). At first glance, such a dependency makes backpropagating the gradients through DLEs more complicated. Interestingly, we prove that the gradients can be exactly derived by solving another DLE in the end, which makes our optimization much simpler and more efficient. Finally, as suggested by [14], the LDS parameters, i.e., the transition and measurement matrices require to be stable and orthogonal, respectively. Under our canonical representation, the stability constraint is reduced to the bound constraint. We then make use of the Cayley-transformation [15] to maintain orthogonality and perform the bound-normalization to accomplish stability. Clustering and sparse coding can be combined with high-level pooling frameworks (e.g., bag-of-systems [11] and spatial-temporal-pyramid-matching [16]) for classifying dynamic textures. Our experiments on such kind of data demonstrate that the proposed methods outperform state-of-the-art techniques in terms of the convergence and classification accuracy.
Summary: the paper proposes a clustering method for linear dynamical systems, based on minimizing the kernalized norm between extended observability spaces.  Since the objective function contains terms involving discrete Lypanunov equations (DLEs), the paper  derives how to pass the derivatives through, yielding a gradient descent algorithm.  Experiments are presented on 2 datasets, for LDS clustering and sparse codebook learning.
Originality:
+1) novelty: the paper is moderately novel, but fairly straightforward. The difference with other related works [3,9,10,11,12] in terms of objective functions, assumptions/constraints, canonical forms should be discussed more.
Quality:
There are a few potential problems in the derivations and motivation.
-1) Theorem 1: The canonical form should have an additional ineqaultiy constraint on Lambda, which is:
   lambda_1 > lambda_2 > lambda_3 > ... lambda_n
which comes from Lambda being a matrix of the singular values of A.  Imposing this constraint removes equivalent representations due to permutations of the state vector.  This inequality constraint could also be included in (12) to truly enforce the canonical form.  However, I think it is not necessary (see next point).
-2) It's unclear why we actually need the canonical form to solve (10).  Since gradient descent is used, we only care that we obtain a feasible solution, and the actual solution that we converge to will depend on the initial starting point.  I suppose that using the canonical form allows for an easier way to handle the stability constraint of A, rho(A)<1, but this needs to be discussed more, and compared with the straightforward approach of directly optimizing (A,C).
-3) Theorem 4: I'm not entirely convinced by the proof.  In the supplemental, Line 35 shows an explicit equation for the vectorized R_12.  Then why in (34) does it need to be transformed into a DLE?  There is something not quite correct about the vectorization and differentiation step. Furthermore, it seems that the gradients could be directly computed from (24). For example, taking the derivative wrt A1:
  d/dA1 (A1^T G12 A2 - G12) = d/dA1 (-C1^T C2)
  G12 A2 + A1^T (dG12/dA1) A2 - (dG12/dA1) = 0
Hence dG12/dA1 can be obtained directly as a DLE.
-4) Given that there are previous works on LDS clustering, experiments are somewhat lacking:
 - Since a kernel method is used, it would be interesting to see the results for directly using the linear kernel, or the other kernels in (19,20).
 - In the video classification experiment, there is no comparison to [3,8,11], which also perform LDS clustering.
 - No comparison with probabilistic clustering methods [21,22].
  
Clarity:
- L210 - Theorem 4 cannot be "directly employed" on new kernels, since the theorem is specific to the kernel in (5). Some extension, or partial re-derivation is needed.
- Other minor typos:
  - Eq 8: it should be mentioned why the k(S_m,S_m) term can be dropped.
  - Eq 9: the minimization is missing z_i.
  - Eq 10: the text is missing how (9) is solved. I'm assuming there are two sub-problems: sparse code estmiation, and codebook estimation with z_i fixed.  (10) corresponds to the second step.
Significance:      
Overall, the approach is reasonable and offers a solution to the problem of clustering LDS. However, more could have been done in terms of relating the work with previous similar methods, exploring other kernel functions, and more thorough comparison in the expeirments.  Some steps in the derivation need to be clarified.