×

A unified approach to computing the nearest complex polynomial with a given zero. (English) Zbl 1329.65095

Summary: Suppose we have a complex polynomial \(f(z)\) whose coefficients are inaccurate, and a prescribed complex number \(\alpha\) such that \(f(\alpha) \neq 0\). We study the problem of computing a complex polynomial \(\widetilde{f}(z)\) such that \(\widetilde{f}(\alpha) = 0\) and the distance between \(\widetilde{f}\) and \(f\), i.e. \(\| \widetilde{f} - f \|\), is minimal. Considering that previous works usually took the usual \(l_p\)-norm, weighted \(l_p\)-norm and block-wise norm as distance measures, we first introduce a new-defined synthetic norm that integrates all these norms. Then, we propose a unified approach to study the proposed problem and succeed in giving explicit expressions of the nearest polynomial. The effectiveness of our approach is illustrated by two examples, one of which shows an extension of finding the nearest complex polynomial with a zero in a given domain. Finally, as an application of the new-defined norm, we discuss a matrix-valued optimization problem that is very common in machine learning.

MSC:

65H04 Numerical computation of roots of polynomial equations
30C10 Polynomials and rational functions of one complex variable
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)

Software:

MultRoot
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Argyriou, A.; Evgeniou, T.; Pontil, M., Convex multi-task feature learning, Mach. Learn., 73, 3, 243-272 (2008) · Zbl 1470.68073
[2] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press · Zbl 1058.90049
[3] Chen, J.; Fan, M. K.H.; Nett, C. N., Structured singular values and stability analysis of uncertain polynomials, part 2: a missing link, Systems Control Lett., 23, 2, 53-65 (1994) · Zbl 0826.93054
[4] Farouki, R. T.; Han, C. Y., Root neighborhoods, generalized lemniscates, and robust stability of dynamic systems, Appl. Algebra Engrg. Comm. Comput., 18, 1-2, 169-189 (2007) · Zbl 1192.65018
[5] Figueiredo, M.; Nowak, R.; Wright, S., Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signal Process., 1, 4, 586-597 (2007)
[6] Gracia, J. M., Nearest matrix with tow prescribed eigenvalues, Linear Algebra Appl., 401, 277-294 (2005) · Zbl 1074.15011
[7] Graillat, S., A note on a nearest polynomial with a given root, ACM SIGSAM Bull., 39, 2, 53-60 (2005) · Zbl 1341.12001
[8] Hitz, M. A.; Kaltofen, E., Efficient algorithms for computing the nearest polynomial with constrained roots, (Proc. 1998 International Symposium on Symbolic and Algebraic Computation. Proc. 1998 International Symposium on Symbolic and Algebraic Computation, ISSAC’98 (1998)), 236-243 · Zbl 0917.65045
[9] Hitz, M. A.; Kaltofen, E.; Lakshman, Y. N., Efficient algorithms for computing the nearest polynomial with a real root and related problems, (Proc. 1999 International Symposium on Symbolic and Algebraic Computation. Proc. 1999 International Symposium on Symbolic and Algebraic Computation, ISSAC’99 (1999)), 205-212
[10] Karmarkar, N.; Lakshman, Y. N., Approximate polynomial greatest common divisors and nearest singular polynomials, (Proc. 1996 International Symposium on Symbolic and Algebraic Computation. Proc. 1996 International Symposium on Symbolic and Algebraic Computation, ISSAC’96 (1996)), 35-39 · Zbl 0928.13017
[11] Karmarkar, N.; Lakshman, Y. N., On approximate GCDs of univariate polynomials, J. Symbolic Comput., 26, 6, 653-666 (1998) · Zbl 0967.12007
[12] Kim, S.; Koh, K.; Lustig, M.; Boyd, S.; Gorinevsky, D., An interior-point method for large-scale \(\ell_1\)-regularized least squares, IEEE J. Sel. Top. Signal Process., 1, 4, 606-617 (2007)
[13] Li, Z.; Zhi, L., Computing the nearest singular univariate polynomials with given root multiplicities, Theoret. Comput. Sci., 479, 150-162 (2013) · Zbl 1291.65082
[14] Luo, Z. X.; Hu, W. Y.; Sheen, D. W., The nearest complex polynomial with a zero in a given complex domain, Theoret. Comput. Sci., 412, 50, 7029-7043 (2011) · Zbl 1228.68066
[15] Mosier, R. G., Root neighborhoods of a polynomial, Math. Comp., 47, 175, 265-273 (1986) · Zbl 0598.65023
[16] Nie, F.; Huang, H.; Cai, X.; Ding, C., Efficient and robust feature selection via joint \(L_{2, 1}\)-norms minimization, (Proc. Neural Information Processing Systems. Proc. Neural Information Processing Systems, NIPS’2010 (2010)), 1813-1821
[17] Pope, S. R.; Szanto, A., Nearest multivariate system with given root multiplicities, J. Symbolic Comput., 44, 6, 606-625 (2009) · Zbl 1168.65347
[18] Qiu, L.; Davison, E. J., A simple procedure for the exact stability robustness computation of polynomials with affine coefficient perturbations, Systems Control Lett., 13, 5, 413-420 (1989) · Zbl 0691.93045
[19] Rezvani, N.; Corless, R. M., The nearest polynomial with a given zero, revisited, ACM SIGSAM Bull., 39, 3, 73-79 (2005) · Zbl 1341.12002
[20] Rezvani, N.; Corless, R. M., Using weighted norms to find nearest polynomials satisfying linear constraints, (Proc. 2011 International Workshop on Symbolic-Numeric Computation (2011)), 81-87 · Zbl 1346.68300
[21] Sekigawa, H., The nearest polynomial with a zero in a given domain, Theoret. Comput. Sci., 409, 2, 282-291 (2008) · Zbl 1156.65046
[22] Sekigawa, H., Computing the nearest polynomial with a zero in a given domain by using piecewise rational functions, J. Symbolic Comput., 46, 12, 1318-1335 (2011) · Zbl 1252.65088
[23] Shi, Z.; Yang, Y.; Guo, Z.; Lai, Z., Face recognition by sparse discriminant analysis via joint \(L_{2, 1}\)-norm minimization, Pattern Recognit., 47, 2447-2453 (2014)
[24] Stetter, H. J., The nearest polynomial with a given zero, and similar problems, ACM SIGSAM Bull., 33, 4, 2-4 (1999) · Zbl 1097.65524
[25] Stetter, H. J., Numerical Polynomial Algebra (2004), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 1058.65054
[26] Yuan, M.; Lin, Y., Model selection and estimation in regression with grouped variables, J. R. Stat. Soc. Ser. B, 68, 49-67 (2006) · Zbl 1141.62030
[27] Zeng, Z., Computing multiple roots of inexact polynomials, Math. Comp., 74, 265-273 (2005)
[28] Sekigawa, H., The nearest polynomial to multiple given polynomials with a given zero, (Proc. 2014 Symposium on Symbolic-Numeric Computation. Proc. 2014 Symposium on Symbolic-Numeric Computation, SNC2014 (2014)), 144-145 · Zbl 1345.68295
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.