Our papers on sparse recovery on graph incidence matrices [1], optimal steady-state control [2], and robustness of consensus algorithms under measurement errors [3] have been accepted to IEEE Conference on Decision and Control. See you in Miami!
![[doi]](https://mallada.ece.jhu.edu/wp-content/plugins/papercite/img/external.png){kind=small}
M. Zhao, M. D. Kaba, R. Vidal, D. R. Robinson, and E. Mallada, “Sparse Recovery over Graph Incidence Matrices,” in 57th IEEE Conference on Decision and Control (CDC), 2018, pp. 364-371. [Bibtex] [Abstract] [Download PDF]
Classical results in sparse representation guarantee the exact recovery of sparse signals under assumptions on the dictionary that are either too strong or NP hard to check. Moreover, such results may be too pessimistic in practice since they are based on a worst-case analysis. In this paper, we consider the sparse recovery of signals defined over a graph, for which the dictionary takes the form of an incidence matrix. We show that in this case necessary and sufficient conditions can be derived in terms of properties of the cycles of the graph, which can be checked in polynomial time. Our analysis further allows us to derive location dependent conditions for recovery that only depend on the cycles of the graph that intersect this support. Finally, we exploit sparsity properties on the measurements to a specialized sub-graph-based recovery algorithm that outperforms the standard $l_1$-minimization.
@inproceedings{zkvrm2018cdc,
abstract = {Classical results in sparse representation guarantee
the exact recovery of sparse signals under assumptions on
the dictionary that are either too strong or NP hard to check.
Moreover, such results may be too pessimistic in practice since
they are based on a worst-case analysis. In this paper, we
consider the sparse recovery of signals defined over a graph,
for which the dictionary takes the form of an incidence matrix.
We show that in this case necessary and sufficient conditions
can be derived in terms of properties of the cycles of the
graph, which can be checked in polynomial time. Our analysis
further allows us to derive location dependent conditions for
recovery that only depend on the cycles of the graph that
intersect this support. Finally, we exploit sparsity properties on
the measurements to a specialized sub-graph-based recovery
algorithm that outperforms the standard $l_1$-minimization.},
author = {Zhao, Mengnan and Kaba, Mustafa Devrim and Vidal, Rene and Robinson, Daniel R. and Mallada, Enrique},
booktitle = {57th IEEE Conference on Decision and Control (CDC)},
doi = {10.1109/CDC.2018.8619666},
grants = {AMPS:1736448},
issn = {2576-2370},
month = {12},
pages = {364-371},
title = {Sparse Recovery over Graph Incidence Matrices},
url = {https://mallada.ece.jhu.edu/pubs/2018-CDC-ZKVRM.pdf},
year = {2018}
}[Bibtex] [Abstract] [Download PDF]
We consider the problem of designing a feedback controller that guides the input and output of a linear timeinvariant system to a minimizer of a convex optimization problem. The system is subject to an unknown disturbance, piecewise constant in time, which shifts the feasible set defined by the system equilibrium constraints. Our proposed design combines proportional-integral control with gradient feedback, and enforces the Karush-Kuhn-Tucker optimality conditions in steady-state without incorporating dual variables into the controller. We prove that the input and output variables achieve optimality in steady-state, and provide a stability criterion based on absolute stability theory. The effectiveness of our approach is illustrated on a simple example system.
@inproceedings{lnms2018cdc,
abstract = {We consider the problem of designing a feedback
controller that guides the input and output of a linear timeinvariant
system to a minimizer of a convex optimization
problem. The system is subject to an unknown disturbance,
piecewise constant in time, which shifts the feasible set defined
by the system equilibrium constraints. Our proposed design
combines proportional-integral control with gradient feedback,
and enforces the Karush-Kuhn-Tucker optimality conditions
in steady-state without incorporating dual variables into the
controller. We prove that the input and output variables achieve
optimality in steady-state, and provide a stability criterion
based on absolute stability theory. The effectiveness of our
approach is illustrated on a simple example system.},
author = {Lawrence, Liam S. P. and Nelson, Zachary and Mallada, Enrique and Simpson-Porco, John W.},
booktitle = {57th IEEE Conference on Decision and Control (CDC)},
doi = {10.1109/CDC.2018.8619812},
grants = {CPS:1544771, ARO:W911NF-17-1-0092, CAREER-1752362},
issn = {2576-2370},
month = {12},
pages = {3251-3257},
title = {Optimal Steady-State Control for Linear Time-Invariant Systems},
url = {https://mallada.ece.jhu.edu/pubs/2018-CDC-LNMS.pdf},
year = {2018}
}[Bibtex] [Abstract] [Download PDF]
Consensus algorithms constitute a powerful tool for computing average values or coordinating agents in many distributed applications. Unfortunately, the same property that allows this computation (i.e., the nontrivial nullspace of the state matrix) leads to unbounded state variance in the presence of measurement errors. In this work, we explore the trade-off between relative and absolute communication (feedback) in the presence of measurement errors. We evaluate the robustness of first and second order integrator systems under a parameterized family of controllers (homotopy) that continuously trade between relative and absolute feedback interconnections in terms of the H2 norm an appropriately defined inputoutput system. Our approach extends the previous H2 norm based analysis to systems with directed feedback interconnections whose underlying weighted graph Laplacians are diagonalizable. Our results indicate that any level of absolute communication is sufficient to achieve a finite H2 norm but that purely relative feedback can only achieve finite norms when the measurement error is not exciting subspace associated with the consensus state. Numerical examples demonstrate that smoothly reducing the proportion of relative feedback in double integrator systems smoothly decreases the system performance and that this performance degradation is more rapid systems with relative feedback in only the first state (position).
@inproceedings{jmg2018cdc,
abstract = {Consensus algorithms constitute a powerful tool for computing average values or coordinating agents in many distributed applications. Unfortunately, the same property that allows this computation (i.e., the nontrivial nullspace of the state matrix) leads to unbounded state variance in the presence of measurement errors. In this work, we explore the trade-off between relative and absolute communication (feedback) in the presence of measurement errors. We evaluate the robustness of first and second order integrator systems under a parameterized family of controllers (homotopy) that continuously trade between relative and absolute feedback interconnections in terms of the H2 norm an appropriately defined inputoutput system. Our approach extends the previous H2 norm based analysis to systems with directed feedback interconnections whose underlying weighted graph Laplacians are diagonalizable. Our results indicate that any level of absolute communication is sufficient to achieve a finite H2 norm but that purely relative feedback can only achieve finite norms when the measurement error is not exciting subspace associated with the consensus state. Numerical examples demonstrate that smoothly reducing the proportion of relative feedback in double integrator systems smoothly decreases the system performance and that this performance degradation is more rapid systems with relative feedback in only the first state (position).},
author = {Ji, Chengda and Mallada, Enrique and Gayme, Dennice},
booktitle = {57th IEEE Conference on Decision and Control (CDC)},
doi = {10.1109/CDC.2018.8619283},
grants = {CPS:1544771, ARO:W911NF-17-1-0092, CAREER-1752362},
issn = {2576-2370},
month = {12},
pages = {1238-1244},
title = {Evaluating Robustness of Consensus Algorithms Under Measurement Error over Digraph},
url = {https://mallada.ece.jhu.edu/pubs/2018-CDC-JMG.pdf},
year = {2018}
}