[{"language":[{"iso":"eng"}],"_id":"14922","oa_version":"Preprint","scopus_import":"1","doi":"10.1109/isit54713.2023.10206899","quality_controlled":"1","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"date_created":"2024-02-02T11:18:40Z","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2303.07245","open_access":"1"}],"department":[{"_id":"MaMo"}],"year":"2023","publication_status":"published","publisher":"IEEE","external_id":{"arxiv":["2303.07245"]},"day":"30","oa":1,"type":"conference","article_processing_charge":"No","title":"Concentration without independence via information measures","arxiv":1,"publication_identifier":{"eissn":["2157-8117"],"eisbn":["9781665475549"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2023-06-30T00:00:00Z","related_material":{"record":[{"id":"15172","status":"public","relation":"later_version"}]},"abstract":[{"lang":"eng","text":"We propose a novel approach to concentration for non-independent random variables. The main idea is to ``pretend'' that the random variables are independent and pay a multiplicative price measuring how far they are from actually being independent. This price is encapsulated in the Hellinger integral between the joint and the product of the marginals, which is then upper bounded leveraging tensorisation properties. Our bounds represent a natural generalisation of concentration inequalities in the presence of dependence: we recover exactly the classical bounds (McDiarmid's inequality) when the random variables are independent. Furthermore, in a ``large deviations'' regime, we obtain the same decay in the probability as for the independent case, even when the random variables display non-trivial dependencies. To show this, we consider a number of applications of interest. First, we provide a bound for Markov chains with finite state space. Then, we consider the Simple Symmetric Random Walk, which is a non-contracting Markov chain, and a non-Markovian setting in which the stochastic process depends on its entire past. To conclude, we propose an application to Markov Chain Monte Carlo methods, where our approach leads to an improved lower bound on the minimum burn-in period required to reach a certain accuracy. In all of these settings, we provide a regime of parameters in which our bound fares better than what the state of the art can provide."}],"citation":{"ista":"Esposito AR, Mondelli M. 2023. Concentration without independence via information measures. Proceedings of 2023 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 400–405.","chicago":"Esposito, Amedeo Roberto, and Marco Mondelli. “Concentration without Independence via Information Measures.” In <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>, 400–405. IEEE, 2023. <a href=\"https://doi.org/10.1109/isit54713.2023.10206899\">https://doi.org/10.1109/isit54713.2023.10206899</a>.","ama":"Esposito AR, Mondelli M. Concentration without independence via information measures. In: <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>. IEEE; 2023:400-405. doi:<a href=\"https://doi.org/10.1109/isit54713.2023.10206899\">10.1109/isit54713.2023.10206899</a>","apa":"Esposito, A. R., &#38; Mondelli, M. (2023). Concentration without independence via information measures. In <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i> (pp. 400–405). Taipei, Taiwan: IEEE. <a href=\"https://doi.org/10.1109/isit54713.2023.10206899\">https://doi.org/10.1109/isit54713.2023.10206899</a>","mla":"Esposito, Amedeo Roberto, and Marco Mondelli. “Concentration without Independence via Information Measures.” <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>, IEEE, 2023, pp. 400–05, doi:<a href=\"https://doi.org/10.1109/isit54713.2023.10206899\">10.1109/isit54713.2023.10206899</a>.","short":"A.R. Esposito, M. Mondelli, in:, Proceedings of 2023 IEEE International Symposium on Information Theory, IEEE, 2023, pp. 400–405.","ieee":"A. R. Esposito and M. Mondelli, “Concentration without independence via information measures,” in <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>, Taipei, Taiwan, 2023, pp. 400–405."},"conference":{"location":"Taipei, Taiwan","name":"ISIT: International Symposium on Information Theory","end_date":"2023-06-30","start_date":"2023-06-25"},"corr_author":"1","date_updated":"2025-09-04T13:06:52Z","status":"public","author":[{"id":"9583e921-e1ad-11ec-9862-cef099626dc9","full_name":"Esposito, Amedeo Roberto","first_name":"Amedeo Roberto","last_name":"Esposito"},{"full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli","orcid":"0000-0002-3242-7020","first_name":"Marco"}],"publication":"Proceedings of 2023 IEEE International Symposium on Information Theory","month":"06","acknowledgement":"The authors are partially supported by the 2019 Lopez-Loreta Prize. They would also like to thank Professor Jan Maas for providing valuable suggestions and comments on an early version of the work.","page":"400-405"},{"arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"eissn":["2157-8117"],"isbn":["9781665475549"]},"title":"Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise","article_processing_charge":"No","oa":1,"day":"30","external_id":{"arxiv":["2302.03306"]},"type":"conference","department":[{"_id":"MaMo"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2302.03306","open_access":"1"}],"publisher":"IEEE","year":"2023","publication_status":"published","date_created":"2024-02-02T11:20:39Z","quality_controlled":"1","oa_version":"Preprint","scopus_import":"1","_id":"14923","doi":"10.1109/isit54713.2023.10206671","language":[{"iso":"eng"}],"page":"1178-1183","month":"06","publication":"Proceedings of 2023 IEEE International Symposium on Information Theory","author":[{"last_name":"Fu","first_name":"Teng","full_name":"Fu, Teng"},{"last_name":"Liu","first_name":"YuHao","full_name":"Liu, YuHao"},{"full_name":"Barbier, Jean","last_name":"Barbier","first_name":"Jean"},{"first_name":"Marco","last_name":"Mondelli","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"},{"first_name":"ShanSuo","last_name":"Liang","full_name":"Liang, ShanSuo"},{"full_name":"Hou, TianQi","first_name":"TianQi","last_name":"Hou"}],"status":"public","date_updated":"2025-07-10T11:51:04Z","conference":{"start_date":"2023-06-25","end_date":"2023-06-30","name":"ISIT: International Symposium on Information Theory","location":"Taipei, Taiwan"},"abstract":[{"text":"We study the performance of a Bayesian statistician who estimates a rank-one signal corrupted by non-symmetric rotationally invariant noise with a generic distribution of singular values. As the signal-to-noise ratio and the noise structure are unknown, a Gaussian setup is incorrectly assumed. We derive the exact analytic expression for the error of the mismatched Bayes estimator and also provide the analysis of an approximate message passing (AMP) algorithm. The first result exploits the asymptotic behavior of spherical integrals for rectangular matrices and of low-rank matrix perturbations; the second one relies on the design and analysis of an auxiliary AMP. The numerical experiments show that there is a performance gap between the AMP and Bayes estimators, which is due to the incorrect estimation of the signal norm.","lang":"eng"}],"citation":{"ista":"Fu T, Liu Y, Barbier J, Mondelli M, Liang S, Hou T. 2023. Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise. Proceedings of 2023 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 1178–1183.","ama":"Fu T, Liu Y, Barbier J, Mondelli M, Liang S, Hou T. Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise. In: <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>. IEEE; 2023:1178-1183. doi:<a href=\"https://doi.org/10.1109/isit54713.2023.10206671\">10.1109/isit54713.2023.10206671</a>","chicago":"Fu, Teng, YuHao Liu, Jean Barbier, Marco Mondelli, ShanSuo Liang, and TianQi Hou. “Mismatched Estimation of Non-Symmetric Rank-One Matrices Corrupted by Structured Noise.” In <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>, 1178–83. IEEE, 2023. <a href=\"https://doi.org/10.1109/isit54713.2023.10206671\">https://doi.org/10.1109/isit54713.2023.10206671</a>.","ieee":"T. Fu, Y. Liu, J. Barbier, M. Mondelli, S. Liang, and T. Hou, “Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise,” in <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>, Taipei, Taiwan, 2023, pp. 1178–1183.","mla":"Fu, Teng, et al. “Mismatched Estimation of Non-Symmetric Rank-One Matrices Corrupted by Structured Noise.” <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>, IEEE, 2023, pp. 1178–83, doi:<a href=\"https://doi.org/10.1109/isit54713.2023.10206671\">10.1109/isit54713.2023.10206671</a>.","short":"T. Fu, Y. Liu, J. Barbier, M. Mondelli, S. Liang, T. Hou, in:, Proceedings of 2023 IEEE International Symposium on Information Theory, IEEE, 2023, pp. 1178–1183.","apa":"Fu, T., Liu, Y., Barbier, J., Mondelli, M., Liang, S., &#38; Hou, T. (2023). Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise. In <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i> (pp. 1178–1183). Taipei, Taiwan: IEEE. <a href=\"https://doi.org/10.1109/isit54713.2023.10206671\">https://doi.org/10.1109/isit54713.2023.10206671</a>"},"corr_author":"1","date_published":"2023-06-30T00:00:00Z"},{"month":"06","title":"A new coding paradigm for the primitive relay channel","arxiv":1,"publication_identifier":{"eissn":["2157-8117"]},"page":"351-355","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1801.03153"}],"author":[{"orcid":"0000-0002-3242-7020","last_name":"Mondelli","first_name":"Marco","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"},{"full_name":"Hassani, Hamed","last_name":"Hassani","first_name":"Hamed"},{"last_name":"Urbanke","first_name":"Rudiger","full_name":"Urbanke, Rudiger"}],"year":"2018","publication_status":"published","publisher":"IEEE","external_id":{"arxiv":["1801.03153"]},"day":"16","publication":"2018 IEEE International Symposium on Information Theory","oa":1,"type":"conference","quality_controlled":"1","extern":"1","date_updated":"2024-10-09T20:59:04Z","date_created":"2019-07-24T09:10:38Z","date_published":"2018-06-16T00:00:00Z","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"7007"}]},"citation":{"ista":"Mondelli M, Hassani H, Urbanke R. 2018. A new coding paradigm for the primitive relay channel. 2018 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory , 351–355.","chicago":"Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “A New Coding Paradigm for the Primitive Relay Channel.” In <i>2018 IEEE International Symposium on Information Theory</i>, 351–55. IEEE, 2018. <a href=\"https://doi.org/10.1109/isit.2018.8437479\">https://doi.org/10.1109/isit.2018.8437479</a>.","ama":"Mondelli M, Hassani H, Urbanke R. A new coding paradigm for the primitive relay channel. In: <i>2018 IEEE International Symposium on Information Theory</i>. IEEE; 2018:351-355. doi:<a href=\"https://doi.org/10.1109/isit.2018.8437479\">10.1109/isit.2018.8437479</a>","apa":"Mondelli, M., Hassani, H., &#38; Urbanke, R. (2018). A new coding paradigm for the primitive relay channel. In <i>2018 IEEE International Symposium on Information Theory</i> (pp. 351–355). Vail, CO, United States: IEEE. <a href=\"https://doi.org/10.1109/isit.2018.8437479\">https://doi.org/10.1109/isit.2018.8437479</a>","short":"M. Mondelli, H. Hassani, R. Urbanke, in:, 2018 IEEE International Symposium on Information Theory, IEEE, 2018, pp. 351–355.","ieee":"M. Mondelli, H. Hassani, and R. Urbanke, “A new coding paradigm for the primitive relay channel,” in <i>2018 IEEE International Symposium on Information Theory</i>, Vail, CO, United States, 2018, pp. 351–355.","mla":"Mondelli, Marco, et al. “A New Coding Paradigm for the Primitive Relay Channel.” <i>2018 IEEE International Symposium on Information Theory</i>, IEEE, 2018, pp. 351–55, doi:<a href=\"https://doi.org/10.1109/isit.2018.8437479\">10.1109/isit.2018.8437479</a>."},"_id":"6675","abstract":[{"lang":"eng","text":"We present a coding paradigm that provides a new achievable rate for the primitive relay channel by combining compress-and-forward and decode-and-forward with a chaining construction. In the primitive relay channel model, the source broadcasts a message to the relay and to the destination; and the relay facilitates this communication by sending an additional message to the destination through a separate channel. Two well-known coding approaches for this setting are decode-and-forward and compress-and-forward: in the former, the relay decodes the message and sends some of the information to the destination; in the latter, the relay does not attempt to decode, but it sends a compressed description of the received sequence to the destination via Wyner-Ziv coding. In our scheme, we transmit over pairs of blocks and we use compress-and-forward for the first block and decode-and-forward for the second. In particular, in the first block, the relay does not attempt to decode and it sends only a part of the compressed description of the received sequence; in the second block, the relay decodes the message and sends this information plus the remaining part of the compressed sequence relative to the first block. As a result, we strictly outperform both compress-and- forward and decode-and-forward. Furthermore, this paradigm can be implemented with a low-complexity polar coding scheme that has the typical attractive features of polar codes, i.e., quasi-linear encoding/decoding complexity and super-polynomial decay of the error probability. Throughout the paper we consider as a running example the special case of the erasure relay channel and we compare the rates achievable by our proposed scheme with the existing upper and lower bounds."}],"conference":{"name":"ISIT: International Symposium on Information Theory ","location":"Vail, CO, United States","end_date":"2018-06-22","start_date":"2018-06-17"},"oa_version":"Preprint","doi":"10.1109/isit.2018.8437479"},{"month":"06","title":"Construction of polar codes with sublinear complexity","arxiv":1,"page":"1853-1857","publication_identifier":{"eissn":["2157-8117"],"isbn":["9781509040964"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1612.05295"}],"author":[{"first_name":"Marco","last_name":"Mondelli","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"},{"full_name":"Hassani, S. Hamed","last_name":"Hassani","first_name":"S. Hamed"},{"first_name":"Rudiger","last_name":"Urbanke","full_name":"Urbanke, Rudiger"}],"year":"2017","publication_status":"published","publisher":"IEEE","external_id":{"arxiv":["1612.05295"]},"day":"15","oa":1,"publication":"2017 IEEE International Symposium on Information Theory ","type":"conference","quality_controlled":"1","date_updated":"2023-02-23T12:49:08Z","extern":"1","date_created":"2019-07-30T07:14:18Z","date_published":"2017-06-15T00:00:00Z","language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"6663"}]},"abstract":[{"lang":"eng","text":"Consider the problem of constructing a polar code of block length N for the transmission over a given channel W. Typically this requires to compute the reliability of all the N synthetic channels and then to include those that are sufficiently reliable. However, we know from [1], [2] that there is a partial order among the synthetic channels. Hence, it is natural to ask whether we can exploit it to reduce the computational burden of the construction problem. We show that, if we take advantage of the partial order [1], [2], we can construct a polar code by computing the reliability of roughly N/ log 3/2 N synthetic channels. Such a set of synthetic channels is universal, in the sense that it allows one to construct polar codes for any W, and it can be identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists in reducing the construction problem to the problem of computing the maximum cardinality of an antichain for a suitable partially ordered set. As such, this method is general and it can be used to further improve the complexity of the construction problem in case a new partial order on the synthetic channels of polar codes is discovered."}],"_id":"6729","citation":{"chicago":"Mondelli, Marco, S. Hamed Hassani, and Rudiger Urbanke. “Construction of Polar Codes with Sublinear Complexity.” In <i>2017 IEEE International Symposium on Information Theory </i>, 1853–57. IEEE, 2017. <a href=\"https://doi.org/10.1109/isit.2017.8006850\">https://doi.org/10.1109/isit.2017.8006850</a>.","ama":"Mondelli M, Hassani SH, Urbanke R. Construction of polar codes with sublinear complexity. In: <i>2017 IEEE International Symposium on Information Theory </i>. IEEE; 2017:1853-1857. doi:<a href=\"https://doi.org/10.1109/isit.2017.8006850\">10.1109/isit.2017.8006850</a>","apa":"Mondelli, M., Hassani, S. H., &#38; Urbanke, R. (2017). Construction of polar codes with sublinear complexity. In <i>2017 IEEE International Symposium on Information Theory </i> (pp. 1853–1857). Aachen, Germany: IEEE. <a href=\"https://doi.org/10.1109/isit.2017.8006850\">https://doi.org/10.1109/isit.2017.8006850</a>","mla":"Mondelli, Marco, et al. “Construction of Polar Codes with Sublinear Complexity.” <i>2017 IEEE International Symposium on Information Theory </i>, IEEE, 2017, pp. 1853–57, doi:<a href=\"https://doi.org/10.1109/isit.2017.8006850\">10.1109/isit.2017.8006850</a>.","ieee":"M. Mondelli, S. H. Hassani, and R. Urbanke, “Construction of polar codes with sublinear complexity,” in <i>2017 IEEE International Symposium on Information Theory </i>, Aachen, Germany, 2017, pp. 1853–1857.","short":"M. Mondelli, S.H. Hassani, R. Urbanke, in:, 2017 IEEE International Symposium on Information Theory , IEEE, 2017, pp. 1853–1857.","ista":"Mondelli M, Hassani SH, Urbanke R. 2017. Construction of polar codes with sublinear complexity. 2017 IEEE International Symposium on Information Theory . ISIT: International Symposium on Information Theory, 1853–1857."},"conference":{"name":"ISIT: International Symposium on Information Theory","location":"Aachen, Germany","end_date":"2017-06-30","start_date":"2017-06-25"},"oa_version":"Preprint","doi":"10.1109/isit.2017.8006850"}]