TY - JOUR

T1 - A sparsification approach to set membership identification of switched affine systems

AU - Ozay, Necmiye

AU - Sznaier, Mario

AU - Lagoa, Constantino M.

AU - Camps, Octavia I.

N1 - Funding Information:
Manuscript received May 31, 2009; revised May 31, 2010; accepted July 17, 2011. Date of publication August 30, 2011; date of current version February 29, 2012. This work was supported in part by the NSF under Grants IIS–0713003, ECCS-0901433, AFOSR Grant FA9550–09–0253 and the Alert DHS Center of Excellence under Award Number 2008-ST-061-ED0001. Recommended by Associate Editor F. Dabbene.

PY - 2012/3

Y1 - 2012/3

N2 - This paper addresses the problem of robust identification of a class of discrete-time affine hybrid systems, switched affine models, in a set membership framework. Given a finite collection of noisy input/output data and some minimal a priori information about the set of admissible plants, the objective is to identify a suitable set of affine models along with a switching sequence that can explain the available experimental information, while minimizing either the number of switches or subsystems. For the case where it is desired to minimize the number of switches, the key idea of the paper is to reduce this problem to a sparsification form, where the goal is to maximize sparsity of a suitably constructed vector sequence. Our main result shows that in the case of ℓ bounded noise, this sparsification problem can be exactly solved via convex optimization. In the general case where the noise is only known to belong to a convex set N, the problem is generically NP-hard. However, as we show in the paper, efficient convex relaxations can be obtained by exploiting recent results on sparse signal recovery. Similarly, we present both a sparsification formulation and a convex relaxation for the (known to be NP hard) case where it is desired to minimize the number of subsystems. These results are illustrated using two non-trivial problems arising in computer vision applications: video-shot and dynamic texture segmentation.

AB - This paper addresses the problem of robust identification of a class of discrete-time affine hybrid systems, switched affine models, in a set membership framework. Given a finite collection of noisy input/output data and some minimal a priori information about the set of admissible plants, the objective is to identify a suitable set of affine models along with a switching sequence that can explain the available experimental information, while minimizing either the number of switches or subsystems. For the case where it is desired to minimize the number of switches, the key idea of the paper is to reduce this problem to a sparsification form, where the goal is to maximize sparsity of a suitably constructed vector sequence. Our main result shows that in the case of ℓ bounded noise, this sparsification problem can be exactly solved via convex optimization. In the general case where the noise is only known to belong to a convex set N, the problem is generically NP-hard. However, as we show in the paper, efficient convex relaxations can be obtained by exploiting recent results on sparse signal recovery. Similarly, we present both a sparsification formulation and a convex relaxation for the (known to be NP hard) case where it is desired to minimize the number of subsystems. These results are illustrated using two non-trivial problems arising in computer vision applications: video-shot and dynamic texture segmentation.

UR - http://www.scopus.com/inward/record.url?scp=84857770002&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84857770002&partnerID=8YFLogxK

U2 - 10.1109/TAC.2011.2166295

DO - 10.1109/TAC.2011.2166295

M3 - Article

AN - SCOPUS:84857770002

SN - 0018-9286

VL - 57

SP - 634

EP - 648

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

IS - 3

M1 - 6004819

ER -